“Games against Nature” [1] are two-player games of perfect information, in which one player's moves are made randomly (here, uniformly); the final payoff to the non-random player is given by some bounded-value function of the move history. Estimating the value of such games under optimal play, and computing near-optimal strategies, is an important goal in the study of decision-making under uncertainty, and has seen significant research in AI and allied areas [2], with only experimental evaluation of most algorithms' performance. The problem's PSPACE-completeness does not rule out nontrivial algorithms. Improved algorithms with theoretical guarantees are known in various cases where the payoff function F has special structure, and Littman, Majercik, and Pitassi [3] give a sampling-based improved algorithm for general F, for turn-orders which restrict the number of non-random player strategies. We study the case of general F for which the players strictly alternate with binary moves-for which the approach of [3] does not improve over brute force. We give a randomized algorithm to approximate the value of such games under optimal play, and to execute near-optimal strategies. Our algorithm, while exponential-time, achieves exponential savings over brute-force, and certifies a lower bound on the game value with exponentially small additive expected error. (On the downside, the constant of improvement in the base of the runtime exponent is tiny, and the algorithm uses exponential space.) Our algorithm is recursive, and bootstraps a “base case” algorithm for fixed-size inputs. The method of recursive composition used, the specific base-case guarantees needed, and the steps to establish these guarantees are interesting and, we feel, likely to find uses beyond the present work.

The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.

We propose a general approach to modelling algorithmic paradigms for the exact solution of NP-hard problems. Our approach is based on polynomial time reductions to succinct versions of problems solvable in polynomial time. We use this viewpoint to explore and compare the power of paradigms such as branching and dynamic programming, and to shed light on the true complexity of various problems. As one instantiation, we model branching using the notion of witness compression, i.e., reducibility to the circuit satisfiability problem parameterized by the number of variables of the circuit. We show this is equivalent to the previously studied notion of `OPP-algorithms', and provide a technique for proving conditional lower bounds for witness compressions via a constructive variant of AND-composition, which is a notion previously studied in theory of preprocessing. In the context of parameterized complexity we use this to show that problems such as Pathwidth and Treewidth and Independent Set parameterized by pathwidth do not have witness compression, assuming NP subseteq coNP/poly. Since these problems admit fast fixed parameter tractable algorithms via dynamic programming, this shows that dynamic programming can be stronger than branching, under a standard complexity hypothesis. Our approach has applications outside parameterized complexity as well: for example, we show if a polynomial time algorithm outputs a maximum independent set of a given planar graph on n vertices with probability exp(-n^{1-epsilon}) for some epsilon>0, then NP subseteq coNP/poly. This negative result dims the prospects for one very natural approach to sub-exponential time algorithms for problems on planar graphs. As two other illustrations (more exploratory) of our approach, we model algorithms based on inclusion-exclusion or group algebras via the notion of "parity compression", and we model a subclass of dynamic programming algorithms with the notion of "disjunctive dynamic programming". These models give us a way to naturally classify various parameterized problems with FPT algorithms. In the case of the dynamic programming model, we show that Independent Set parameterized by pathwidth is complete for this model.

Given an instance of a hard decision problem, a limited goal is to compress that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $\mathrm{OR}$-compression scheme for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some “target” language $L'$ if and only if $\bigvee_j [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is strong if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$. Strong compression for SAT seems unlikely. Work of Harnik and Naor [SIAM J. Comput., 39 (2010), pp. 1667--1713] and Bodlaender, Downey, Fellows, and Hermelin [J. Comput. System Sci., 75 (2009), pp. 423--434] showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam [J. Comput. System Sci., 77 (2011), pp. 91--106] showed that if SAT is strongly OR-compressible, then $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Finding similar evidence against AND-compression was left as an open question. We provide such evidence: we show that strong AND- or OR-compression for SAT would imply nonuniform, statistical zero-knowledge proofs for SAT---an even stronger and more unlikely consequence than $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Our method applies against probabilistic compression schemes of sufficient “quality” with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of quantum instance compression, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, “preserves the answer” to the input instance. The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to “disguise” information being fed into a compressive mapping; we believe this method may find other applications.

We study the computation power of the congested clique, a model of distributed computation where n players communicate with each other over a complete network in order to compute some function of their inputs. The number of bits that can be sent on any edge in a round is bounded by a parameter b We consider two versions of the model: in the first, the players communicate by unicast, allowing them to send a different message on each of their links in one round; in the second, the players communicate by broadcast, sending one message to all their neighbors.

We prove the following surprising result: given any quantum state $\rho$ on $n$ qubits, there exists a local Hamiltonian $H$ on $\operatorname*{poly}(n)$ qubits (e.g., a sum of two-qubit interactions), such that any ground state of $H$ can be used to simulate $\rho$ on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that ${BQP/qpoly}\subseteq{QMA/poly}$, which supersedes the previous result of Aaronson that ${BQP/qpoly}\subseteq {PP/poly}$. Indeed, we can exactly characterize quantum advice as equivalent in power to untrusted quantum advice combined with trusted classical advice. Proving our main result requires combining a large number of previous tools---including a result of Alon et al. on learning of real-valued concept classes, a result of Aaronson on the learnability of quantum states, and a result of Aharonov and Regev on “${QMA}_{{+}}$ super-verifiers''---and also creating some new ones. The main new tool is a so-called majority-certificates lemma, which is closely related to boosting in machine learning, and which seems likely to find independent applications. In its simplest version, this lemma says the following. Given any set $S$ of Boolean functions on $n$ variables, any function $f\in S$ can be expressed as the pointwise majority of $m=O(n)$ functions $f_{1},\ldots,f_{m}\in S$, such that each $f_{i}$ is the unique function in $S$ compatible with $O(\log\vert S\vert)$ input/output constraints.

We give two nondeterministic reductions which yield new direct product theorems (DPTs) for Boolean circuits. In these theorems one assumes that a target function F is mildly hard against nondeterministic circuits, and concludes that the direct product Ft is extremely hard against (only polynomially smaller) probabilistic circuits. The main advantage of these results compared with previous DPTs is the strength of the size bound in our conclusion. As an application, we show that if NP is not in coNP/poly then, for every PPT algorithm attempting to produce satisfying assigments to Boolean formulas, there are infinitely many instances where the algorithm's success probability is nearly-exponentially small. This furthers a project of Paturi and Pudlák [STOC'10].

We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show sharp limitations of several existing lowerbound methods for this model. First, we study an information-theoretic lower-bound method due to Cherukhin, that yields bounds of form Ωd(n · λd-1(n)) on the number of wires needed to compute cyclic convolutions in depth d ≥ 2. This was the first improvement over the lower bounds provided by the well-known superconcentrator technique (for d = 2, 3 and for even d ≥ 4). Cherukhin's method was formalized by Jukna as a general lower-bound criterion for Boolean operators, the “Strong Multiscale Entropy” (SME) property. It seemed plausible that this property could imply significantly better lower bounds by an improved analysis. However, we show that this is not the case, by exhibiting an explicit operator with the SME property that is computable in depth d with O(n · λd-1(n)) wires, for d = 2, 3 and for even d ≥ 6. Next, we show limitations of two simpler lower-bound criteria given by Jukna: the “entropy method” for general operators, and the “pairwise-distance method” for linear operators. We show that neither method gives super-linear lower bounds for depth 3. In the process, we obtain the first known polynomial separation between the depth-2 and depth-3 wire complexities for an explicit operator. We also continue the study (initiated by Jukna) of the complexity of “representing” a linear operator by bounded-depth circuits, a weaker notion than computing the operator.

Given an instance of a hard decision problem, a limited goal is to compress that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas ψ1,⋯,ψt, we must determine if at least one ψjis satisfiable. An OR-compression scheme for SAT is a polynomial-time reduction that maps (ψ1,⋯,ψt) to a string z, such that z lies in some “target” language L' if and only if Vj[ψj∈SAT] holds. (Here, L' can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is strong if |z| is polynomially bounded in n = maxj|ψj|, independent of t. Strong compression for SAT seems unlikely. Work of Harnik and Naor (FOCS '06/SICOMP '10) and Bodlaender, Downey, Fellows, and Hermelin (ICALP '08/JCSS '09) showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam (STOC '08/JCSS '11) showed that if SAT is strongly OR-compressible, then NP C coNP/poly. Finding similar evidence against AND-compression was left as an open question. We provide such evidence: we show that strong AND- or OR-compression for SAT would imply non-uniform, statistical zero-knowledge proofs for SAT-an even stronger and more unlikely consequence than NP ⊆ coNP/poly. Our method applies against probabilistic compression schemes of sufficient “quality” with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of quantum instance compression, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, “preserves the answer” to the input instance. The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language L in order to fool a cheating prover in a proof system for L̅. Our key technical tool is a new method to “disguise” information being fed into a compressive mapping; we believe this method may find other applications.

We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of x. First, we study the problem of successfully predicting a single 0 from among the bits of x. In our model we have only one chance to make a prediction, but may do so at a time of our choosing. This model is applicable to a variety of situations in which we want to perform an action of fixed duration, and need to predict a "safe" time-interval to perform it.

We consider a distributed task allocation problem in which m players must divide a set of n tasks between them. Each player i receives as input a set Xi of tasks such that the union of all input sets covers the task set. The goal is for each player to output a subset Yi ⊆ Xi, such that the outputs (Y1,...,Ym) form a partition of the set of tasks. The problem can be viewed as a distributed one-shot variant of the well-known k-server problem, and we also show that it is closely related to the problem of finding a rooted spanning tree in directed broadcast networks.

The "direct product problem" is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1 - ε in computing the Boolean function f on input distribution μ, then for α ≤ 1, every αεTk-query algorithm has success probability at most (2αε(1 - ε))kin computing the fc-fold direct product f⊗kcorrectly on k independent inputs from μ. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. Using this DPT, we show that for an absolute constant α >; 0, the worst-case success probability of any αR2(f)k-query randomized algorithm for f⊗kfalls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k). Our proof technique involves defining and analyzing a collec tion of martingales associated with an algorithm attempting to solve f⊗k. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.

We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly is contained in QMA/poly, which supersedes the previous result of Aaronson that BQP/qpoly is contained in PP/poly. Indeed, we can exactly characterize quantum advice, as equivalent in power to untrusted quantum advice combined with trusted classical advice.

In Direct Sum problems |8|, one tries to show that for a given computational model, the complexity of computing a collection F = {f1(x1),hellipf1(x1)} of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ways in which the joint computational complexity can behave when all the fiare evaluated on a common input. We focus on the deterministic decision tree model, with depth as the complexity measure; in this model we prove a result to the effect that the 'obvious' constraints on joint computational complexity are essentially the only ones. The proof uses an intriguing new type of cryptographic data structure called a `mystery bin' which we construct using a small polynomial separation between deterministic and unambiguous query complexity shown by Savicky. We also pose a variant of the Direct Sum Conjecture of |8| which, if proved for a single family of functions, could yield an analogous result for models such as the communication model.

The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. *We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given O tilde(radicn) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on Dinur's version of the PCP Theorem and is inherently non-relativizing. *We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all kges=2. *We give evidence that QMA(2) sube PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.