A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted \(k\)xor problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant \(k\). Thus for such \(k\), the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.

An inequality by Samorodnitsky states that if f:F2n → ℝ is a nonnegative function, and S ⊆ [n] is chosen by randomly including each coordinate with probability a certain λ = λ(q,ρ) < 1, then log||Tρf||q ≤ ES log||E(f|S)||q. Samorodnitsky’s inequality has several applications to the theory of error-correcting codes. Perhaps most notably, it can be used to show that any binary linear code (with minimum distance ω(logn)) that has vanishing decoding error probability on the BEC(λ) (binary erasure channel) also has vanishing decoding error on all memoryless symmetric channels with capacity above some C = C(λ).

We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let $T$ be any (possibly infinite) bounded set of vectors in $\mathbb{R}^n$, and let $\{\boldsymbol{X}_t := t \cdot \boldsymbol{g} \}_{t\in T}$ be the canonical Gaussian process on $T$, where $\boldsymbol{g}\sim N(0, I_n)$. We show that there is an $O_\varepsilon(1)$-size subset $S \subseteq T$ and a set of real values $\{c_s\}_{s \in S}$ such that the random variable $\sup_{s \in S} \{\boldsymbol{X}_s + c_s\}$ is an $\varepsilon$-approximator\,(in $L^1$) of the random variable $\sup_{t \in T} {\boldsymbol{X}}_t$. Notably, the size of the sparsifier $S$ is completely independent of both $|T|$ and the ambient dimension $n$. We give two applications of this sparsification theorem: - A "Junta Theorem" for Norms: We show that given any norm $ν(x)$ on $\mathbb{R}^n$, there is another norm $ψ(x)$ depending only on the projection of $x$ onto $O_\varepsilon(1)$ directions, for which $ψ({\boldsymbol{g}})$ is a multiplicative $(1 \pm \varepsilon)$-approximation of $ν({\boldsymbol{g}})$ with probability $1-\varepsilon$ for ${\boldsymbol{g}} \sim N(0,I_n)$. - Sparsification of Convex Sets: We show that any intersection of (possibly infinitely many) halfspaces in $\mathbb{R}^n$ that are at distance $r$ from the origin is $\varepsilon$-close (under $N(0,I_n)$) to an intersection of only $O_{r,\varepsilon}(1)$ halfspaces. This yields new polynomial-time \emph{agnostic learning} and \emph{tolerant property testing} algorithms for intersections of halfspaces.

A fundamental task in quantum information science is state certification: testing whether a lab-prepared n-qubit state is close to a given hypothesis state. In this work, we show that every pure hypothesis state can be certified using only O(n^2) single-qubit measurements applied to O(n) copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024).

In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ℓ∞-Short Integer Solution (SIS∞) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups.

We consider the task of quantum state certification: given a description of a hypothesis state σ and multiple copies of an unknown state ρ, a tester aims to determine whether the two states are equal or є-far in trace distance. It is known that Θ(d/є2) copies of ρ are necessary and sufficient for this task, assuming the tester can make entangled measurements over all copies. However, these bounds are for a worst-case σ, and it is not known what the optimal copy complexity is for this problem on an instance-by-instance basis. While such instance-optimal bounds have previously been shown for quantum state certification when the tester is limited to measurements unentangled across copies, they remained open when testers are unrestricted in the kind of measurements they can perform.

We describe a quantum algorithm for the Planted Noisy kXOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (4th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings [Has20], by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy kXOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks.

We study the problem of finding a (pure) product state with optimal fidelity to an unknown $n$-qubit quantum state $ρ$, given copies of $ρ$. This is a basic instance of a fundamental question in quantum learning: is it possible to efficiently learn a simple approximation to an arbitrary state? We give an algorithm which finds a product state with fidelity $\varepsilon$-close to optimal, using $N = n^{\text{poly}(1/\varepsilon)}$ copies of $ρ$ and $\text{poly}(N)$ classical overhead. We further show that estimating the optimal fidelity is NP-hard for error $\varepsilon = 1/\text{poly}(n)$, showing that the error dependence cannot be significantly improved. For our algorithm, we build a carefully-defined cover over candidate product states, qubit by qubit, and then demonstrate that extending the cover can be reduced to approximate constrained polynomial optimization. For our proof of hardness, we give a formal reduction from polynomial optimization to finding the closest product state. Together, these results demonstrate a fundamental connection between these two seemingly unrelated questions. Building on our general approach, we also develop more efficient algorithms in three simpler settings: when the optimal fidelity exceeds $5/6$; when we restrict ourselves to a discrete class of product states; and when we are allowed to output a matrix product state.

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$-close to the unknown unitary in diamond norm. We design an algorithm achieving error $\varepsilon$ using $O\left(\mathrm{~d}^{2} / \varepsilon\right)$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)$ [via standard process tomography] or $O\left(\mathrm{~d}^{2.5} / \varepsilon\right)$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce $\varepsilon$-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega\left(\mathrm{d}^{2} / \varepsilon\right)$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.

We give a strongly explicit construction of ϵ approximate k-designs for the orthogonal group O(N) and the unitary group U(N), for $N=2^{n}$. Our designs are of cardinality $\operatorname{poly}(N^{k}/\epsilon)$ (equivalently, they have seed length $O(nk+\log(1/\epsilon)))$; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

Suppose y is a real random variable, and one is given access to “the code” that generates it (for example, a randomized or quantum circuit whose output is y). We give a quantum procedure that runs the code O(n) times and returns an estimate for μ = E[y] that with high probability satisfies , where σ = stddev[y]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse . Our method improves upon previous works, which either made additional assumptions about y, and/or assumed the algorithm knew an a priori bound on σ, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover's algorithm but with complex phases. * The full version of the paper can be accessed at https://arxiv.org/abs/2208.07544

Let $Φ$ be an irreducible root system (other than $G_2$) of rank at least $2$, let $\mathbb{F}$ be a finite field with $p = \operatorname{char} \mathbb{F} > 3$, and let $\mathrm{G}(Φ,\mathbb{F})$ be the corresponding Chevalley group. We describe a strongly explicit high-dimensional expander (HDX) family of dimension $\mathrm{rank}(Φ)$, where $\mathrm{G}(Φ,\mathbb{F})$ acts simply transitively on the top-dimensional faces; these are $λ$-spectral HDXs with $λ\to 0$ as $p \to \infty$. This generalizes a construction of Kaufman and Oppenheim (STOC 2018), which corresponds to the case $Φ= A_d$. Our work gives three new families of spectral HDXs of any dimension $\ge 2$, and four exceptional constructions of dimension $4$, $6$, $7$, and $8$.

We revisit the basic problem of quantum state certification: given copies of unknown mixed state ρ∈ℂ^{d×d} and the description of a mixed state σ, decide whether σ=ρ or ‖σ−ρ‖_𝗍𝗋 ≥ ϵ. When σ is maximally mixed, this is mixedness testing, and it is known that Ω(d^{Θ(1)}/ϵ^2) copies are necessary, where the exact exponent depends on the type of measurements the learner can make [OW15, BCL20], and in many of these settings there is a matching upper bound [OW15, BOW19, BCL20]. Can one avoid this d^{Θ(1)} dependence for certain kinds of mixed states σ, e.g. ones which are approximately low rank? More ambitiously, does there exist a simple functional f : ℂ^{d×d} → ℝ_{≥0} for which one can show that Θ(f(σ)/ϵ^2) copies are necessary and sufficient for state certification with respect to any σ? Such instance-optimal bounds are known in the context of classical distribution testing, e.g. [VV17]. Here we give the first bounds of this nature for the quantum setting, showing (up to log factors) that the copy complexity for state certification using nonadaptive incoherent measurements is essentially given by the copy complexity for mixedness testing times the fidelity between σ and the maximally mixed state. Surprisingly, our bound differs substantially from instance optimal bounds for the classical problem, demonstrating a qualitative difference between the two settings.

We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over~$\{\pm 1\}^n$. For each model $\mathcal{M}$, we identify the "high-probability value"~$s^*_{\mathcal{M}}$ of the natural SDP relaxation (equivalently, the quantum value). That is, for all $\varepsilon > 0$ we show that the SDP optimum of a random $n$-variable instance is (when normalized by~$n$) in the range $(s^*_{\mathcal{M}}-\varepsilon, s^*_{\mathcal{M}}+\varepsilon)$ with high probability. Our class of models includes non-regular CSPs, and ones where the SDP relaxation value is strictly smaller than the spectral relaxation value.

For an abelian group H acting on the set [𝓁], an (H,𝓁)-lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H. Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are non-explicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019]. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit d-regular expander graphs G obtained from an (H,𝓁)-lift of a (suitable) base n-vertex expander G₀ with the following parameters: ii) λ(G) ≤ 2√{d-1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε), iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depth-first search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.

The fundamental problem in much of physics and quantum chemistry is to optimize a low-degree polynomial in certain anticommuting variables. Being a quantum mechanical problem, in many cases we do not know an efficient classical witness to the optimum, or even to an approximation of the optimum. One prominent exception is when the optimum is described by a so-called “Gaussian state”, also called a free fermion state. In this work we are interested in the complexity of this optimization problem when no good Gaussian state exists. Our primary testbed is the Sachdev–Ye–Kitaev (SYK) model of random degree-q polynomials, a model of great current interest in condensed matter physics and string theory, and one which has remarkable properties from a computational complexity standpoint. Among other results, we give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the q=4 SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue; both algorithms achieve constant-factor approximations with high probability.

We give a pseudorandom generator that fools m -facet polytopes over {0, 1} n with seed length polylog( m ) · log n . The previous best seed length had superlinear dependence on m .

For every constant $d \geq 3$ and $\epsilon > 0$, we give a deterministic $\operatorname{poly}(n)$-time algorithm that outputs a $d$-regular graph on $\Theta(n)$ vertices that is $\eps$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2\sqrt{d-1} + \epsilon$ (excluding the single trivial eigenvalue of $d$).

We study the problem of learning an unknown mixture of k permutations over n elements, given access to noisy samples drawn from the unknown mixture. We consider a range of different noise models, including natural variants of the “heat kernel” noise framework and the Mallows model. We give an algorithm which, for each of these noise models, learns the unknown mixture to high accuracy under mild assumptions and runs in $n^{O(log k)}$ time. Our approach is based on a new procedure that recovers an unknown mixture of permutations from noisy higher-order marginals.

Approximate Counting refers to the problem where we are given query access to a function f : [N] → {0,1}, and we wish to estimate K = #{x : f(x) = 1} to within a factor of 1+ε (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with O(min (√{N/ε}, √{N/K} / ε) queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve O(√{N/ε}) query complexity, which is tight.

We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum ”Threshold Search” algorithm that requires only O((log2 m)/є2) samples of a d-dimensional state ρ. That is, given observables 0 ≤ A1, A2, …, Am ≤ 1 such that (ρ Ai) ≥ 1/2 for at least one i, the algorithm finds j with (ρ Aj) ≥ 1/2−є. As a consequence, we obtain a Shadow Tomography algorithm requiring only O((log2 m)(logd)/є4) samples, which simultaneously achieves the best known dependence on each parameter m, d, є. This yields the same sample complexity for quantum Hypothesis Selection among m states; we also give an alternative Hypothesis Selection method using O((log3 m)/є2) samples.

We present a quantum LDPC code family that has distance Ω(N3/5/polylog(N)) and Θ(N3/5) logical qubits, where N is the code length. This is the first quantum LDPC code construction that achieves distance greater than N1/2 polylog(N). The construction is based on generalizing the homological product of codes to a fiber bundle.

Let p(Y1, ..., Yd, Z1, ..., Ze) be a self-adjoint noncommutative polynomial, with coefficients from Cr×r, in the indeterminates Y1,..., Yd (considered to be self-adjoint), the indeterminates Z1, ..., Ze, and their adjoints Z1*, ..., Ze*. Suppose Y1, ..., Yd are replaced by independent random n x n matching matrices, and Z1, ..., Ze are replaced by independent random n x n permutation matrices. Assuming for simplicity that p's coefficients are 0-1 matrices, the result can be thought of as a kind of random rn-vertex graph G. As n goes to infinity, there will be a natural limiting infinite graph X that covers any finite outcome for G. A recent landmark result of Bordenave and Collins shows that for any , with high probability the spectrum of a random G will be eps-close in Hausdorff distance to the spectrum of X (once the suitably defined “trivial” eigenvalues are excluded). We say that G is “eps-near fully X-Ramanujan”. Our work has two contributions: First we study and clarify the class of infinite graphs X that can arise in this way. Second, we derandomize the Bordenave-Collins result: for any X, we provide explicit, arbitrarily large graphs G that are covered by X and that have (nontrivial) spectrum at Hausdorff distance at most eps from that of X. This significantly generalizes the recent work of Mohanty et al., which provided explicit near-Ramanujan graphs for every degree d (meaning d-regular graphs with all nontrivial eigenvalues bounded in magnitude by 2sqrt(d-1) + eps). As an application of our main technical theorem, we are also able to determine the “eigenvalue relaxation value” for a wide class of average-case degree-2 constraint satisfaction problems.

Let X be an infinite graph of bounded degree; e.g., the Cayley graph of a free product of finite groups. If G is a finite graph covered by X, it is said to be X-Ramanujan if its second-largest eigenvalue λ2(G) is at most the spectral radius ρ(X) of X, and more generally k-quasi-X-Ramanujan if λk (G) is at most ρ(X). In case X is the infinite Δ-regular tree, this reduces to the well known notion of a finite Δ-regular graph being Ramanujan. Inspired by the Interlacing Polynomials method of Marcus, Spielman, and Srivastava, we show the existence of infinitely many k-quasi-X-Ramanujan graphs for a variety of infinite X. In particular, X need not be a tree; our analysis is applicable whenever X is what we call an additive product graph. This additive product is a new construction of an infinite graph A1 ⌖ ··· ⌖ Ac from finite “atom” graphs A1, …,Ac over a common vertex set. It generalizes the notion of the free product graph A1 * · · · * Ac when the atoms Aj are vertex-transitive, and it generalizes the notion of the universal covering tree when the atoms Aj are single-edge graphs. Key to our analysis is a new graph polynomial α(A1,…,Ac; x) that we call the additive characteristic polynomial. It generalizes the well known matching polynomial μ(G; x) in case the atoms Aj are the single edges of G, and it generalizes the r-characteristic polynomial introduced in [Rav16, LR18]. We show that α(A1, …, Ac; x) is real-rooted, and all of its roots have magnitude at most ρ(A1 ⌖ ··· ⌖ Ac). This last fact is proven by generalizing Godsil's notion of treelike walks on a graph G to a notion of freelike walks on a collection of atoms A1, …, Ac.

We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, "two-eigenvalue 2CSPs". We show this SDP value coincides with the spectral relaxation value, possibly indicating a computational threshold. Our analysis extends the previously resolved cases of random regular 2XOR and NAE-3SAT, and includes new cases such as random Sort₄ (equivalently, CHSH) and Forrelation CSPs. Our techniques include new generalizations of the nonbacktracking operator, the Ihara-Bass Formula, and the Friedman/Bordenave proof of Alon’s Conjecture.

We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length d O(logd) · logn. All previous generators had a seed length with at least a 2 d dependence on d.

Let $G$ be any $n$-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by $1/\sqrtΔ$ (for example, a random graph $G$ of average degree~$Θ(Δ)$ typically has this property). We show that the $\exp\Big(c \frac{\log n}{\log Δ}\Big)$-round Sherali--Adams linear programming hierarchy certifies that the maximum cut in such a~$G$ is at most $50.1\%$ (in fact, at most $\tfrac12 + 2^{-Ω(c)}$). For example, in random graphs with $n^{1.01}$ edges, $O(1)$ rounds suffice; in random graphs with $n \cdot \text{polylog}(n)$ edges, $n^{O(1/\log \log n)} = n^{o(1)}$ rounds suffice. Our results stand in contrast to the conventional beliefs that linear programming hierarchies perform poorly for \maxcut and other CSPs, and that eigenvalue/SDP methods are needed for effective refutation. Indeed, our results imply that constant-round Sherali--Adams can strongly refute random Boolean $k$-CSP instances with $n^{\lceil k/2 \rceil + δ}$ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.

Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficiencies related to global constraints. First, they were not able to support a "cardinality constraint", as in, say, the Min-Bisection problem. Second, while the pseudoexpectation of the objective function was shown to have some value beta, it did not necessarily actually "satisfy" the constraint "objective = beta". In this paper we show how to remedy both deficiencies in the case of random CSPs, by translating global constraints into local constraints. Using these ideas, we also show that degree-Omega(sqrt{n}) SOS does not provide a (4/3 - epsilon)-approximation for Min-Bisection, and degree-Omega(n) SOS does not provide a (11/12 + epsilon)-approximation for Max-Bisection or a (5/4 - epsilon)-approximation for Min-Bisection. No prior SOS lower bounds for these problems were known.

Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has the property that spectral/SDP algorithms can efficiently refute random instances when the constraint density is a large constant (with high probability). But do these methods work immediately above the “satisfiability threshold”, or is there still a range of constraint densities for which random NAE-3SAT instances are unsatisfiable but hard to refute? We show that the latter situation prevails, at least in the context of random regular instances and SDP-based refutation. More precisely, whereas a random d-regular instance of NAE-3SAT is easily shown to be unsatisfiable (whp) once d ≥ 8, we establish the following sharp threshold result regarding efficient refutation: If d < 13.5 then the basic SDP, even augmented with triangle inequalities, fails to refute satisfiability (whp); if d > 13.5 then even the most basic spectral algorithm refutes satisfiability (whp).

We consider the problem of quantum state certification, where one is given n copies of an unknown d-dimensional quantum mixed state ρ, and one wants to test whether ρ is equal to some known mixed state σ or else is є-far from σ. The goal is to use notably fewer copies than the Ω(d2) needed for full tomography on ρ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using n = O(d/є) copies, and one with respect to trace distance using n = O(d/є2) copies. The latter algorithm also applies when σ is unknown as well. These copy complexities are optimal up to constant factors.

We give a pseudorandom generator that fools m-facet polytopes over {0,1}n with seed length polylog(m) · log(n). The previous best seed length had superlinear dependence on m. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any {0,1}-integer program.

A probability distribution over {-1, 1}^n is (epsilon, k)-wise uniform if, roughly, it is epsilon-close to the uniform distribution when restricted to any k coordinates. We consider the problem of how far an (epsilon, k)-wise uniform distribution can be from any globally k-wise uniform distribution. We show that every (epsilon, k)-wise uniform distribution is O(n^{k/2}epsilon)-close to a k-wise uniform distribution in total variation distance. In addition, we show that this bound is optimal for all even k: we find an (epsilon, k)-wise uniform distribution that is Omega(n^{k/2}epsilon)-far from any k-wise uniform distribution in total variation distance. For k=1, we get a better upper bound of O(epsilon), which is also optimal. One application of our closeness result is to the sample complexity of testing whether a distribution is k-wise uniform or delta-far from k-wise uniform. We give an upper bound of O(n^{k}/delta^2) (or O(log n/delta^2) when k = 1) on the required samples. We show an improved upper bound of O~(n^{k/2}/delta^2) for the special case of testing fully uniform vs. delta-far from k-wise uniform. Finally, we complement this with a matching lower bound of Omega(n/delta^2) when k = 2. Our results improve upon the best known bounds from [Alon et al., 2007], and have simpler proofs.

Aaronson and Drucker (2011) asked whether there exists a quantum finite automaton that can distinguish fair coin tosses from biased ones by spending significantly more time in accepting states, on average, given an infinite sequence of tosses. We answer this question negatively.

Suppose we want to minimize a polynomial p(x) = p(x_1,...,x_n), subject to some polynomial constraints q_1(x),...,q_m(x) >_ 0, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include x_i^2 <_ 1 for all 1 <_ i <_ n. It is often stated that the degree-d version of the SOS hierarchy can be solved, to high accuracy, in time n^O(d). Indeed, I myself have stated this in several previous works. The point of this note is to state (or remind the reader) that this is not obviously true. The difficulty comes not from the "r" in the Ellipsoid Algorithm, but from the "R"; a priori, we only know an exponential upper bound on the number of bits needed to write down the SOS solution. An explicit example is given of a degree-2 SOS program illustrating the difficulty.

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that \MIPone[k,c,s] \subseteq \PSPACE provided s/c \leq (.62-o(1))k/2^k, resolving a question of Austrin, H\aa stad, and Pass. Here \MIPone[k,c,s] is the class of languages decidable with completeness c and soundness s by an interactive proof system with k provers, each constrained to communicate just 1 bit.

In the (deletion-channel) trace reconstruction problem, there is an unknown n-bit source string x. An algorithm is given access to independent traces of x, where a trace is formed by deleting each bit of x independently with probability δ. The goal of the algorithm is to recover x exactly (with high probability), while minimizing samples (number of traces) and running time.

Let P:{0,1}k → {0,1} be a nontrivial k-ary predicate. Consider a random instance of the constraint satisfaction problem (P) on n variables with Δ n constraints, each being P applied to k randomly chosen literals. Provided the constraint density satisfies Δ ≫ 1, such an instance is unsatisfiable with high probability. The refutation problem is to efficiently find a proof of unsatisfiability.

We continue our analysis of: (i) "Quantum tomography", i.e., learning a quantum state, i.e., the quantum generalization of learning a discrete probability distribution; (ii) The distribution of Young diagrams output by the RSK algorithm on random words. Regarding (ii), we introduce two powerful new tools: first, a precise upper bound on the expected length of the longest union of k disjoint increasing subsequences in a random length-n word with letter distribution α1 ≥ α2 ≥ … ≥ αd. Our bound has the correct main term and second-order term, and holds for all n, not just in the large-n limit. Second, a new majorization property of the RSK algorithm that allows one to analyze the Young diagram formed by the lower rows λk, λk+1, … of its output. These tools allow us to prove several new theorems concerning the distribution of random Young diagrams in the nonasymptotic regime, giving concrete error bounds that are optimal, or nearly so, in all parameters. As one example, we give a fundamentally new proof of the celebrated fact that the expected length of the longest increasing sequence in a random length-n permutation is bounded by 2√n. This is the k = 1, αi ≡ 1/d, d → ∞ special case of a much more general result we prove: the expected length of the kth Young diagram row produced by an α-random word is αk n ± 2√αkd n.

Let f(x) = f(x_1, ..., x_n) = sum_{|S|<=k} a_S prod_{i in S} x_i be an n-variate real multilinear polynomial of degree at most k, where S subseteq [n] = {1, 2, ..., n}. For its one-block decoupled version, vf(y,z) = sum_{abs(S)<=k} a_S sum_{i in S}} y_i prod_{j in S\{i}} z_j, we show tail-bound comparisons of the form Pr(abs(vf)(y,z)) > C_k t} <= D_k Pr(abs(f(x)) > t). Our constants C_k, D_k are significantly better than those known for "full decoupling". For example, when x, y, z are independent Gaussians we obtain C_k = D_k = O(k); when x, by, z are +/-1 random variables we obtain C_k = O(k^2), D_k = k^{O(k)}. By contrast, for full decoupling only C_k = D_k = k^{O(k)} is known in these settings. We describe consequences of these results for query complexity (related to conjectures of Aaronson and Ambainis) and for analysis of Boolean functions (including an optimal sharpening of the DFKO Inequality).

In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed quantum state ρ, given few copies. We show that O(d/ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d/ε2) ≤ O(d2/ε2) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d3/ε2) copies for full tomography, and even on the best known prior result of O(d2log(d/ε)/ε2) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension.

We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2 Omega(D^{-3/4}) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a mu + Omega(1/sqrt(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment.

An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.

Let P be a k-ary predicate over a finite alphabet. Consider a random CSP(P) instance I over n variables with m constraints. When m ≫ n the instance will be unsatisfiable with high probability and we want to find a certificate of unsatisfiability. When P is the 3-ary OR predicate, this is the well-studied problem of refuting random 3-SAT formulas and an efficient algorithm is known only when m ≫ n3/2. Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a k-ary predicate, having m ≫≫n[k/2]constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if P fails to support a t-wise uniform distribution, then there is an efficient algorithm that refutes random CSP(P) instances whp when m ≫ nt/2. Indeed, our algorithm will “somewhat strongly” refute the instance I, certifying Opt(I) ≤ 1 - Ωk(1). If t = k then we get the strongest possible refutation, certifying Opt(I) ≤ E[P] + o(1). This last result is new even for random k-SAT. Prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP(P) may be impossible when m ≫ nt/2; thus there is an indication that our algorithm's dependence on m is optimal for every P, at least in the context of SDP hierarchies. As an application of our result, we falsify assumptions used to show hardness-of-learning in recent work of Daniely, Linial, and Shalev-Shwartz.

Let X1, ..., Xnbe joint {±1}-valued random variables. It is known that conditioning on a random subset of O(1/ε2) of them reduces their average pairwise covariance to below ε (in expectation). We conjecture that O(1/ε2) can be improved to O(1/ε). The motivation for the problem and our conjectured improvement comes from the theory of global correlation rounding for convex relaxation hierarchies. We suggest attempting the conjecture in the case that X1, ..., Xnare the leaves of an information flow tree. We prove the conjecture in the case that the information flow tree is a caterpillar graph (similar to a two-state hidden Markov model).

In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given n copies of a mixed state ρ∈ Cd x d and the goal is to distinguish (with high probability) whether ρ's spectrum satisfies some property P or whether it is at least ε-far in l1-distance from satisfying P. This problem was promoted under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions.

Furthering the study of cryptography in constant parallel time, we give new evidence for the security of Gold Reich's candidate pseudorandom generator with near-optimal, polynomial stretch. Our evidence consists both of security against sub exponential-time linear attacks as well as sub exponential-time attacks using SDP hierarchies such as Sherali-Adams+ and Lasserre/Parrilo. More specifically, instantiating Gold Reich's generator with the 5-ary "Tri-Sum-And" predicate, we get a candidate 5-local PRG which is secure against both linear attacks and attacks based on the Lasserre/Parrilo SDP hierarchy. Previous works with such small locality gave polynomially less stretch and were only shown to be secure against linear attacks. Our result is essentially optimal, as known SDP/spectral techniques show the generator would not be secure if its stretch was higher by any polynomial factor. More generally, we show that (a slight variant of) Gold Reich's generator can have stretch increasing with the degree of the smallest nonzero Fourier coefficient of the predicate while resisting sub exponential-time attacks based on the Sherali-Adams+ SDP hierarchy. Again, the dependence on the degree is (potentially) optimal due to known SDP/spectral methods which succeed at any polynomially higher stretch. Finally, for a large family of predicates we also extend this result to security against the much stronger Lasserre/Parrilo SDP hierarchy.

In this work, we study the parity complexity measures pCmin[f] and PDT[f]. Pcmin[f] is the parity kill number of f, the fewest number of parities on the input variables one has to fix in order to "kill" f, i.e. To make it constant. PDT[f] is the depth of the shortest emph{parity decision tree} which computes f. These complexity measures have in recent years become increasingly important in the fields of communication complexity [1], [2], [3], [4] and pseudorandomness [5], [6], [7]. Our main result is a composition theorem for pCmin. The k-th power of f, denoted f^{circ k}, is the function which results from composing f with itself k times. We prove that if f is not a parity function, then pCmin[f^{circ k}] geq Omega(Cmin[f]^{k}). In other words, the parity kill number of f is essentially super multiplicative in the normal kill number of f (also known as the minimum certificate complexity). As an application of our composition theorem, we show lower bounds on the parity complexity measures of sort^{circ k} and HI^{circ k}. Here sort is the sort function due to Ambainis [8], and HI is Kushilevitz's hemi-icosahedron function [9]. In doing so, we disprove a conjecture of Montanaro and Osborne [2] which had applications to communication complexity and computational learning theory. In addition, we give new lower bounds for conjectures of [2], [3] and [4].

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On the other hand, Say and Yakaryilmaz showed that computation with just 1 classical CTC bit gives the power of "postselection", thereby upgrading classical randomized computation (BPP) to the complexity class BPP_path and standard quantum computation (BQP) to the complexity class PP. It is natural to ask whether increasing the number of CTC bits from 1 to 2 (or 3, 4, etc.) leads to increased computational power. We show that the answer is no: randomized computation with logarithmically many CTC bits (i.e., polynomially many CTC states) is equivalent to BPP_path. (Similarly, quantum computation augmented with logarithmically many classical CTC bits is equivalent to PP.) Spoilsports with no interest in time travel may view our results as concerning the robustness of the class BPP_path and the computational complexity of sampling from an implicitly defined Markov chain.

Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant 0 < γ ≤ 1/4, the SOS/Lasserre SDP hierarchy at degree certifies the statement “the maximum independent set in the Frankl–Rödl graph has fractional size o(1)”. Here is the graph with V = {0,1}n and (x,y) ∊ E whenever Δ(x, y) = (1 – γ)n (an even integer). In particular, we show the degree-4 SOS algorithm certifies the chromatic number lower bound “ ”, even though is the canonical integrality gap instance for which standard SDP relaxations cannot even certify “ ”. Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

We consider the problem of estimating the surface area of an unknown n-dimensional set F given membership oracle access. In contrast to previous work, we do not assume that F is convex, and in fact make no assumptions at all about F. By necessity this means that we work in the property testing model; we seek an algorithm which, given parameters A and ∊, satisfies: if surf(F) ≤ A then the algorithm accepts (whp); if F is not ∊-close to some set G with surf (G) ≤ κA, then the algorithm rejects (whp). We call κ ≥ 1 the “approximation factor” of the testing algorithm. The n = 1 case (in which “surf(F) = 2m” means F is a disjoint union of m intervals) was introduced by Kearns and Ron [KR98], who solved the problem with κ = 1/∊ and O(1/∊) oracle queries. Later, Balcan et al. [BBBY12] solved it with with κ = 1 and O(1/∊4) queries. We give the first result for higher dimensions n. Perhaps surprisingly, our algorithm completely evades the “curse of dimensionality”: for any n and any κ > we give a test that uses O(1/∊) queries. For small n we have improved bounds. For n = 1 we can achieve κ = 1 with O(1/∊3.5) queries (slightly improving [BBBY12]), or any κ > 1 with O(1/∊) queries (improving [KR98]). For n = 2,3 we obtain κ ≈ 1.08,1.125 respectively, with O(1/∊) queries. Getting an arbitrary κ > 1 for n > 1 remains an open problem.

Building on work of Cai, Fürer, and Immerman [18], we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic n-vertex graphs G and H such that any sum-of-squares (SOS) proof of nonisomorphism requires degree Ω(n). In other words, we show an Ω(n)-round integrality gap for the Lasserre SDP relaxation. In fact, we show this for pairs G and H which are not even (1 – 10−14)-isomorphic. (Here we say that two n-vertex, m-edge graphs G and H are α-isomorphic if there is a bijection between their vertices which preserves at least αm edges.) Our second result is that under the R3XOR Hypothesis [23] (and also any of a class of hypotheses which generalize the R3XOR Hypothesis), the robust Graph Isomorphism is hard. I.e. for every ∊ > 0, there is no efficient algorithm which can distinguish graph pairs which are (1 — ∊)-isomorphic from pairs which are not even (1 – ∊0)-isomorphic for some universal constant ∊0. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.

This special section contains five selected papers from the 50th Annual Symposium on Foundations of Computer Science (FOCS 2010) sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing. The conference was held in Las Vegas, Nevada, October 23-26, 2010. The conference program consisted of 81 papers, which the program committee selected from 270 submissions. The program committee was composed of Scott Aaronson, Dorit Aharonov, Eli Ben-Sasson, Julia Chuzhoy, Ryan O'Donnell, Roberto Grossi, Nick Harvey, Adam Kalai, Nicole Immorlica, Yuval Ishai, Lap Chi Lau, James Lee, Tal Malkin, Joe Mitchell, Dana Moshkovitz, S. Muthukrishnan, Christos Papadimitriou, Sofya Raskhodnikova, Steve Skiena, Mikkel Thorup, Luca Trevisan, and Eric Vigoda. Each of the five papers appearing in this issue was subject to the standard refereeing process of the SIAM Journal on Computing. In “The Monotone Complexity of $k$-Clique on Random Graphs," Ben Rossman proves that monotone circuits that solve the $k$-clique problem in random graphs must have size $\omega(n^{k/4})$, establishing the first average-case monotone lower bound. Andreas Björklund, in the paper “Determinant Sums for Undirected Hamiltonicity," develops the first improvement to the $\tilde O(2^n)$ dynamic programming algorithm for Hamiltonian circuit: Björklund's algorithm runs in time $\tilde O(1.657^n)$. The paper “Distance Oracles Beyond the Thorup--Zwick Bound" by Mihai Pătraşcu and Liam Roditty presents the first improvement in ten years for the problem of compactly representing an approximation to all-pairs shortest path distances in a graph. Shaddin Dughmi and Tim Roughgarden show how to convert any approximation algorithm for a certain class of problems into a truthful mechanism in the paper “Black-Box Randomized Reductions in Algorithmic Mechanism Design." Ioannis Koutis, Gary Miller, and Richard Peng, in the paper “Approaching Optimality for Solving SDD Linear Systems," present a new nearly linear time algorithm for the problem of solving systems of linear equations that are symmetric and diagonally dominant. We wish to thank Madhu Sudan and Leonard Schulman, the former and current Editors-in-Chief of SICOMP, for being very generous with their time as they helped us in this project. We also wish to thank Heather Blythe of SIAM and the anonymous referees.

Let bS = bX_1 + ·s + bX_n be a sum of n independent integer random variables bX_i, where each bX_i is supported on 0, 1, ·, k-1 but otherwise may have an arbitrary distribution (in particular the bX_i's need not be identically distributed). How many samples are required to learn the distribution bS to high accuracy? In this paper we show that the answer is completely independent of n, and moreover we give a computationally efficient algorithm which achieves this low sample complexity. More precisely, our algorithm learns any such bS to ε-accuracy (with respect to the total variation distance between distributions) using poly(k, 1/ε) samples, independent of n. Its running time is poly(k, 1/ε) in the standard word RAM model. Thus we give a broad generalization of the main result of DDS12stoc which gave a similar learning result for the special case k=2 (when the distribution bS is a Poisson Binomial Distribution). Prior to this work, no nontrivial results were known for learning these distributions even in the case k=3. A key difficulty is that, in contrast to the case of k = 2, sums of independent 0, 1, 2-valued random variables may behave very differently from (discretized) normal distributions, and in fact may be rather complicated - they are not log-concave, they can be θ(n)-modal, there is no relationship between Kolmogorov distance and total variation distance for the class, etc. Nevertheless, the heart of our learning result is a new limit theorem which characterizes what the sum of an arbitrary number of arbitrary independent 0, 1, ·, k-1-valued random variables may look like. Previous limit theorems in this setting made strong assumptions on the "shift invariance" of the random variables bX_i in order to force a discretized normal limit. We believe that our new limit theorem, as the first result for truly arbitrary sums of independent 0, 1, ·, k-1-valued random variables, is of independent interest.

This work is concerned with the proof-complexity of certifying that optimization problems do not have good solutions. Specifically we consider bounded-degree “Sum of Squares” (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof is automatizable using semidefinite programming (SDP), meaning that any n-variable degree-d proof can be found in time nO(d). Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the “d/2-round Lasserre value” of an optimization problem is equal to the best bound provable using a degree-d SOS proof. These ideas were exploited in a recent paper by Barak et al. (STOC 2012) which shows that the known “hard instances” for the Unique-Games problem are in fact optimally solved by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al. can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot–Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor .952 (> .878) using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?

We generalize the Kahn--Kalai--Linial (KKL) theorem to random walks on Cayley and Schreier graphs, making progress on an open problem of Hoory, Linial, and Wigderson. In our generalization, the underlying group need not be abelian so long as the generating set is a union of conjugacy classes. An example corollary is that for every $f : \binom{[n]}{k} \to \{0,1\}$ with ${\bf E}[f]$ and $k/n$ bounded away from $0$ and $1$, there is a pair $1 \leq i < j \leq n$ such that ${\cal I}_{ij}(f) \geq \Omega(\frac{\log n}{n})$. Here ${\cal I}_{ij}(f)$ denotes the “influence” on $f$ of swapping the $i$th and $j$th coordinates. Using this corollary we obtain a “robust” version of the Kruskal--Katona theorem: Given a constant-density subset $A$ of a middle slice of the Hamming $n$-cube, the density of $\partial A$ is greater by at least $\Omega(\frac{\log n}{n})$, unless $A$ is noticeably correlated with a single coordinate. As an application of these results, we show that the set of functions $\{0, 1, x_1, \dots, x_n, \mathrm{Maj}\}$ is a $(1/2 - \gamma)$-net for the set of all $n$-bit monotone Boolean functions, where $\gamma = \Omega(\frac{\log n}{\sqrt{n}})$. This distance is optimal for polynomial-size nets and gives an optimal weak-learning algorithm for monotone functions under the uniform distribution, solving a problem of Blum, Burch, and Langford.

We study the problem of matrix isomorphism of matrix Lie algebras (MatIsoLie). Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley -- Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set L of matrices that is closed under linear combinations and the operation [A, B] = AB - BA. Two matrix Lie algebras L, L' are matrix isomorphic if there is an invertible matrix M such that conjugating every matrix in L by M yields the set L'. We show that certain cases of MatIsoLie -- for the wide and widely studied classes of semi simple and abelian Lie algebras -- are equivalent to graph isomorphism and linear code equivalence, respectively. On the other hand, we give polynomial-time algorithms for other cases of MatIsoLie, which allow us to mostly derandomize a recent result of Kayal on affine equivalence of polynomials.

We say that an algorithm robustly decides a constraint satisfaction problem Π if it distinguishes at-least-(1 -ε)-satisfiable instances from less-than-(1 - r(ε))-satisfiable instances for some function r(ε) with r(ε) → 0 as ε → 0. In this paper we show that the canonical linear programming relaxation robustly decides Π if and only if Π has "width 1" (in the sense of Feder and Vardi).

We show that distinguishing 1/2-satisfiable Unique-Games instances from (3/8 + ε)-satisfiable instances is NP-hard (for all ε > 0). A consequence is that we match or improve the best known c vs. s NP-hardness result for Unique-Games for all values of c (except for c very close to 0). For these c, ours is the first hardness result showing that it helps to take the alphabet size larger than 2. Our NP-hardness reductions are quasilinear-size and thus show nearly full exponential time is required, assuming the ETH.

Consider an optimization problem with $n$ binary variables and $d+1$ linear objective functions. Each valid solution $x \in \{0,1\}^n$ gives rise to an objective vector in $\R^{d+1}$, and one often wants to enumerate the Pareto optima among them. In the worst case there may be exponentially many Pareto optima; however, it was recently shown that in (a generalization of) the smoothed analysis framework, the expected number is polynomial in $n$. Unfortunately, the bound obtained had a rather bad dependence on $d$, roughly $n^{d!}$. We show a significantly improved bound of $n^{2d}$. Our proof is based on defining an algorithm, which we call the $\mathtt{Witness}$ mapping. This algorithm runs on the data and produces an event, in the form of a testimony, that serves as a concise description of what caused a Pareto optimum. We prove that given any testimony, we can check the values of a strict subset of the random variables in the input and deduce some information about the remaining random variables. Hence the $\mathtt{Witness}$ mapping is predictable because, given the output and just some of the input random variables, we can deduce information about the remaining inputs. This immediately implies that any particular testimony is unlikely to occur. We can in fact regard prior work on this problem as being based on a similar principle. Here we are able to prove much stronger bounds because we minimize the description complexity of the output of $\mathtt{Witness}$.

In 1997, Hastad showed NP-hardness of (1 - ε, 1/q + δ)-approximating Max-3Lin(Zq); however it was not until 2007 that Guruswami and Raghavendra were able to show NP-hardness of (1 - ε, δ)- approximating Max-3Lin(Z). In 2004, Khot-Kindler-Mossel-O'Donnell showed UG-hardness of (1 - ε, δ) approximating Max-2Lin(Zq) for q = q(ε, δ) a sufficiently large constant; however achieving the same hardness for Max-2Lin(Z) was given as an open problem in Raghavendra's 2009 thesis. In this work we show that fairly simple modifications to the proofs of the Max-3Lin(Zq) and Max-2Lin(Zq) results yield optimal hardness results over Z. In fact, we show a kind of "bicriteria" hardness: even when there is a (1 - ε) good solution over Z, it is hard for an algorithm to find a 5-good solution over Z, M, or Zmfor any m ≥ q(ε, δ) of the algorithm's choosing.

Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness results for the problem of fnding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in ℝn × {– 1, 1}. We prove that for any constants d ≥ 1, ∊ > 0, Assuming the Unique Games Conjecture, no polynomial-time algorithm can fnd a degree-d PTF that is consistent with a (1/2 + ∊) fraction of a given set of labeled examples in ℝn × {–1, 1}, even if there exists a degree-d PTF that is consistent with a 1 − ∊ fraction of the examples. It is NP-hard to fnd a degree-2 PTF that is consistent with a (1/2 + ∊) fraction of a given set of labeled examples in ℝn × {– 1, 1}, even if there exists a half-space (degree-1 PTF) that is consistent with a 1 − ∊ fraction of the examples. These results immediately imply the following hardness of learning results: (i) Assuming the Unique Games Conjecture, there is no better-than-trivial proper learning algorithm that agnostically learns degree-d PTFs under arbitrary distributions; (ii) There is no better-than-trivial learning algorithm that outputs degree-2 PTFs and agnostically learns halfspaces (i.e. degree-1 PTFs) under arbitrary distributions.

Consider an optimization problem with n binary variables and d+1 linear objective functions. Each valid solution x ∈{0,1}n gives rise to an objective vector in Rd+1, and one often wants to enumerate the Pareto optima among them. In the worst case there may be exponentially many Pareto optima; however, it was recently shown that in (a generalization of) the smoothed analysis framework, the expected number is polynomial in~n. Unfortunately, the bound obtained had a rather bad dependence on d; roughly ndd. In this paper we show a significantly improved bound of n2d.

We present a range of new results for testing properties of Boolean functions that are defined in terms of the Fourier spectrum. Broadly speaking, our results show that the property of a Boolean function having a concise Fourier representation is locally testable. We give the first efficient algorithms for testing whether a Boolean function has a sparse Fourier spectrum (small number of nonzero coefficients) and for testing whether the Fourier spectrum of a Boolean function is supported in a low-dimensional subspace of $\mathbb{F}_2^n$. In both cases we also prove lower bounds showing that any testing algorithm—even an adaptive one—must have query complexity within a polynomial factor of our algorithms, which are nonadaptive. Building on these results, we give an “implicit learning” algorithm that lets us test any subproperty of Fourier concision. We also present some applications of these results to exact learning and decoding. Our technical contributions include new structural results about sparse Boolean functions and new analysis of the pairwise independent hashing of Fourier coefficients from [V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 563–576].

In [Proceedings of the Second Symposium on Switching Circuit Theory and Logical Design (FOCS), 1961, pp. 34–38], Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow parameters. Providing an algorithmic version of Chow's theorem—i.e., efficiently constructing a representation of a threshold function given its Chow parameters—has remained open ever since. This problem has received significant study in the fields of circuit complexity, game theory and the design of voting systems, and learning theory. In this paper we effectively solve the problem, giving a randomized polynomial-time approximation scheme with the following behavior: Given the Chow parameters of a Boolean threshold function f over n bits and any constant $\epsilon>0$, the algorithm runs in time $O(n^2\log^2n)$ and with high probability outputs a representation of a threshold function $f'$ which is $\epsilon$-close to f. Along the way we prove several new results of independent interest about Boolean threshold functions. In addition to various structural results, these include $\tilde{O}(n^2)$-time learning algorithms for threshold functions under the uniform distribution in the following models: (i) the restricted focus of attention model, answering an open question of Birkendorf et al.; (ii) an agnostic-type model. This contrasts with recent results of Guruswami and Raghavendra who show NP-hardness for the problem under general distributions; (iii) the PAC model, with constant $\epsilon$. Our $\tilde{O}(n^2)$-time algorithm substantially improves on the previous best known running time and nearly matches the $\Omega(n^2)$ bits of training data that any successful learning algorithm must use.

We prove new lower bounds in the area of property testing of boolean functions. Specifically, we study the problem of testing whether a boolean function f is isomorphic to a fixed function g (i.e., is equal to g up to permutation of the input variables). The analogous problem for testing graphs was solved by Fischer in 2005. The setting of boolean functions, however, appears to be more difficult, and no progress has been made since the initial study of the problem by Fischer et al. in 2004. Our first result shows that any non-adaptive algorithm for testing isomorphism to a function that "strongly" depends on k variables requires log k - O(1) queries (assuming k/n is bounded away from 1). This lower bound affirms and strengthens a conjecture appearing in the 2004 work of Fischer et al. Its proof relies on total variation bounds between hypergeometric distributions which may be of independent interest. Our second result concerns the simplest interesting case not covered by our first result: non-adaptively testing isomorphism to the Majority function on k variables. Here we show that Ω(k1/12) queries are necessary (again assuming k/n is bounded away from 1). The proof of this result relies on recently developed multidimensional invariance principle tools.

... under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes any product of discrete distributions with probabilities bounded away from 0. Our first main result shows that a recent pseudorandom generator construction of Meka and Zuckerman [MZ09], when suitably modified, can fool arbitrary functions of d halfspaces under product distributions where each coordinate has bounded fourth moment. To ǫ-fool any size-s, depth-d decision tree of halfspaces, our pseudorandom generator uses seed length O((dlog(ds/ǫ)+logn)·log(ds/ǫ)). For monotone functions of d halfspaces, the seed length can be improved to O((dlog(d/ǫ)+logn)·log(d/ǫ)). We get better bounds for larger ǫ; for example, to1/polylog(n)-foolallmonotonefunctionsof(logn)/loglognhalfspaces,ourgeneratorrequires a seed of length just O(logn). Our second main result generalizes the work of Diakonikolas et al. [DGJ + 09] to show that bounded independence suffices to fool functions of halfspaces under product distributions. Assuming each coordinatesatisfiesacertainstrongermoment condition, we showthat anyfunction computable by a size-s, depth-d decision tree of halfspaces is ǫ-fooled by Õ(d4 s 2 /ǫ 2)-wise independence. Our technical contributions include: a new multidimensional version of the classical Berry-Esseen theorem; a derandomization thereof; a generalization of Servedio [Ser07]’s regularity lemma for halfspaceswhichworksunderanyproduct distribution with bounded fourth moments; an extension of this regularity lemma to functions of many halfspaces; and, new analysis of the sandwiching polynomials technique of Bazzi [Baz09] for arbitrary product distributions.

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e., a function of the form $f(x)=\mathrm{sgn}(w\cdot x-\theta)$. We consider halfspaces over the continuous domain $\mathbf{R}^n$ (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube $\{-1,1\}^n$ (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are $\epsilon$-far from any halfspace using only $\mathrm{poly}(\frac{1}{\epsilon})$ queries, independent of the dimension n. Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: The first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube $\{-1,1\}^n$ (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over $\{-1,1\}^n$ poses significant additional complications and requires other ingredients. These include “cross-consistency” versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pp. 103–112].

We generalize the Kahn-Kalai-Linial (KKL) Theorem to random walks on Cayley and Schreier graphs, making progress on an open problem of Hoory, Linial, and Wigderson. In our generalization, the underlying group need not be abelian so long as the generating set is a union of conjugacy classes. An example corollary is that for every f : (k[n]) ¿ {0,1} with E[f] and k/n bounded away from 0 and 1, there is a pair 1 ¿ iij(f) ¿ ¿(log n/n). Here lij(f) denotes the "influence" on / of swapping the ith and jth coordinates. Using this corollary we obtain a "robust" version of the Kruskal-Katona Theorem: Given a constant-density subset A of a middle slice of the Hamming n-cube, the density of ¿A is greater by at least ¿(log n/n), unless A is noticeably correlated with a single coordinate. As an application of these results, we show that the set of functions {0,1, x1,..., x¿, Maj} is a (1/2-¿)-net for the set of all n-bit monotone boolean functions, where ¿ = ¿(log n//¿(n)). This distance is optimal for polynomial-size nets and gives an optimal weak-learning algorithm for monotone functions under the uniform distribution, solving a problem of Blum, Burch and Langford.

This paper addresses the problem of testing whether a Boolean-valued function ƒ is a halfspace, i.e. a function of the form ƒ(x) = sgn(w · x – θ). We consider halfspaces over the continuous domain Rn (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1, 1}n (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are ∊-far from any halfspace using only poly queries, independent of the dimension n. Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: the first gives an exact relationship between the expected value of a halfspace ƒ and the sum of the squares of ƒ's degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube {–1, 1}n (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over {–1, 1}n poses significant additional complications and requires other ingredients. These include “cross-consistency” versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [FKR+02].

In the conclusion of his monumental paper on optimal inapproximability results, Håstad [13] suggested that Fourier analysis of Dictator (Long Code) Tests may not be universally applicable in the study of CSPs. His main open question was to determine if the technique could resolve the approximability of satisfiable 3-bit constraint satisfaction problems. In particular, he asked if the “Not Two” (NTW) predicate is non-approximable beyond the random assignment threshold of 5/8 on satisfiable instances. Around the same time, Zwick [30] showed that all satisfiable 3-CSPs are 5/8-approximable and conjectured that the 5/8 is optimal. In this work we show that Fourier analysis techniques can produce a Dictator Test based on NTW with completeness 1 and soundness 5/8. Our test's analysis uses the Bonami-Gross-Beckner hypercontractive inequality. We also show a soundness lower bound of 5/8 for all 3-query Dictator Tests with perfect completeness. This lower bound for Property Testing is proved in part via a semidefinite programming algorithm of Zwick [30]. Our work precisely determines the 3-query “Dictatorship Testing gap”. Although this represents progress on Zwick's conjecture, current PCP “outer verifier” technology is insufficient to convert our Dictator Test into an NP-hardness-of-approximation result.

In this paper we study a fundamental open problem in the area of probabilistic checkable proofs: What is the smallest s such that NP ⊆ naPCP1,s[O(log n),3]? In the language of hardness of approximation, this problem is equivalent to determining the smallest s such that getting an s-approximation for satisfiable 3-bit constraint satisfaction problems ("3-CSPs") is NP-hard. The previous best upper bound and lower bound for s are 20/27+µ by Khot and Saket [KS06], and 5/8 (assuming NP subseteq BPP) by Zwick [Zwi98]. In this paper we close the gap assuming Khot's d-to-1 Conjecture. Formally, we prove that if Khot's d-to-1 Conjecture holds for any finite constant integer d, then NP naPCP1,5/8+ µ[O(log n),3] for any constant µ > 0. Our conditional result also solves Hastad's open question [Has01] on determining the inapproximability of satisfiable Max-NTW ("Not Two") instances and confirms Zwick's conjecture [Zwi98] that the 5/8-approximation algorithm for satisfiable 3-CSPs is optimal.

What is the least surface area of a shape that tiles Ropfdunder translations by Zopfd? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Omega(radicd). Our main result is a construction with surface area O(radicd), matching the lower bound up to a constant factor of 2radic2pi/eap3. The best previous tile known was only slightly better than the cube, having surface area on the order of d. We generalize this to give a construction that tiles Ropfdby translations of any full rank discrete lattice Lambda with surface area 2piparV-1parfb, where V is the matrix of basis vectors of Lambda, and par.parfbdenotes the Frobenius norm. We show that our bounds are optimal within constant factors for rectangular lattices. Our proof is via a random tessellation process, following recent ideas of Raz in the discrete setting. Our construction gives an almost optimal noise-resistant rounding scheme to round points in Ropfdto rectangular lattice points.

We study the learnability of sets in Ropfnunder the Gaussian distribution, taking Gaussian surface area as the "complexity measure" of the sets being learned. Let CSdenote the class of all (measurable) sets with surface area at most S. We first show that the class CSis learnable to any constant accuracy in time nO(S2), even in the arbitrary noise ("agnostic'') model. Complementing this, we also show that any learning algorithm for CSinformation-theoretically requires 2Omega(S2)examples for learning to constant accuracy. These results together show that Gaussian surface area essentially characterizes the computational complexity of learning under the Gaussian distribution. Our approach yields several new learning results, including the following (all bounds are for learning to any constant accuracy): The class of all convex sets can be agnostically learned in time 2O~(radicn)(and we prove a 2Omega(radicn)lower bound for noise-free learning). This is the first subexponential time algorithm for learning general convex sets even in the noise-free (PAC) model. Intersections of k halfspaces can be agnostically learned in time nO(logk)(cf. Vempala's nO(k)time algorithm for learning in the noise-free model).Cones (with apex centered at the origin), and spheres witharbitrary radius and center, can be agnostically learned in time poly(n).

This article accompanies a tutorial talk given at the 40th ACM STOC conference. In it, we give a brief introduction to Fourier analysis of boolean functions and then discuss some applications: Arrow's Theorem and other ideas from the theory of Social Choice; the Bonami-Beckner Inequality as an extension of Chernoff/Hoeffding bounds to higher-degree polynomials; and, hardness for approximation algorithms.

In the 2nd Annual FOCS (1961), C. K. Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow Parameters. Providing an algorithmic version of Chow's theorem --- i.e., efficiently constructing a representation of a threshold function given its Chow Parameters --- has remained open ever since. This problem has received significant study in the fields of circuit complexity, game theory and the design of voting systems, and learning theory. In this paper we effectively solve the problem, giving a randomized PTAS with the following behavior: Theorem: Given the Chow Parameters of a Boolean threshold function f over n bits and any constant ε > 0, the algorithm runs in time O(n2 log2 n) and with high probability outputs a representation of a threshold function f' which is ε-close to f. Along the way we prove several new results of independent interest about Boolean threshold functions. In addition to various structural results, these include the following new algorithmic results in learning theory (where threshold functions are usually called "halfspaces"): An ~O(n2)-time uniform distribution algorithm for learning halfspaces to constant accuracy in the "Restricted Focus of Attention" (RFA) model of Ben-David et al. [3]. This answers the main open question of [6]. An O(n2)-time agnostic-type learning algorithm for halfspaces under the uniform distribution. This contrasts with recent results of Guruswami and Raghavendra [21] who show that the learning problem we solve is NP-hard under general distributions. As a special case of the latter result we obtain the fastest known algorithm for learning halfspaces to constant accuracy in the uniform distribution PAC learning model. For constant ε our algorithm runs in time ~O(n2), which substantially improves on previous bounds and nearly matches the Ω(n2) bits of training data that any successful learning algorithm must use.

Let G be an undirected graph for which the standard Max-Cut SDP relaxation achieves at least a c fraction of the total edge weight, 1/2 ≤ c ≤ 1. If the actual optimal cut for G is at most an s fraction of the total edge weight, we say that (c, s) is an SDP gap. We define the SDP gap curve GapSDP : [1/2,1] -> [1/2,1] by GapSDP(c) = inf{s : (c, s) is an SDP gap}. In this paper we complete a long line of work [15, 14, 20, 36, 19, 17, 13, 28] by determining the entire SDP gap curve; we show GapSDP(c) = S(c) for a certain explicit (but complicated to state) function S. In particular, our lower bound GapSDP(c) - S(c) is proved via a polynomial-time - RPR2' algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is RPR2 confirms a conjecture of Feige and Langberg [17]. We also describe and analyze the tight connection between SDP gaps and Long Code tests (and the constructions of [25, 3, 4]). Using this connection, we give optimal Long Code tests for Max-Cut. Combining these with results implicit in [27, 29] and ideas from [19], we derive the following conclusions: - The Max-Cut SDP gap curve subject to triangle inequalities is also given by S(c). - No RPR2 algorithm can be guaranteed to find cuts of value larger than S(c) in graphs where the optimal cut is c. (Contrast this with the fact that in the graphs exhibiting the c vs. S(c) SDP gap, our RPR2 algorithm actually finds the optimal cut.) - Further, no polynomial-time algorithm of any kind can have such a guarantee, assuming P ≠ NP and the Unique Games Conjecture.

We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. [Proceedings of the $26$th Annual Symposium on Theory of Computing (STOC), Montréal, QC, 1994, ACM, New York, pp. 273–282]. We give a $\operatorname{poly}(n/\epsilon)$-time algorithm for learning a mixture of k arbitrary product distributions over the n-dimensional Boolean cube $\{0,1\}^n$ to accuracy $\epsilon$, for any constant k. Previous polynomial-time algorithms could achieve this only for $k = 2$ product distributions; our result answers an open question stated independently in [M. Cryan, Learning and Approximation Algorithms for Problems Motivated by Evolutionary Trees, Ph.D. thesis, University of Warwick, Warwick, UK, 1999] and [Y. Freund and Y. Mansour, Proceedings of the $12$th Annual Conference on Computational Learning Theory, 1999, pp. 183–192]. We further give evidence that no polynomial-time algorithm can succeed when k is superconstant, by reduction from a difficult open problem in PAC (probably approximately correct) learning. Finally, we generalize our $\operatorname{poly}(n/\epsilon)$-time algorithm to learn any mixture of $k = O(1)$ product distributions over $\{0,1, \dots, b-1\}^n$, for any $b = O(1)$.

Motivated by the study of parallel repetition and also by the unique games conjecture, we investigate the value of the "odd cycle games" under parallel repetition. Using tools from discrete harmonic analysis, we show that after d rounds on the cycle of length m, the value of the game is at most 1-(1/m)ldrOmega macr(radicd) (for dlesm2, say). This beats the natural barrier of 1-Theta(1/m)2ldrd for Raz-style proofs and also the SDP bound of Feige-Lovasz; however, it just barely fails to have implications for unique games. On the other hand, we also show that improving our bound would require proving nontrivial lower bounds on the surface area of high-dimensional foams. Specifically, one would need to answer: what is the least surface area of a cell that tiles Rdby the lattice Zd?

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX‐CUT to within a factor of $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here $\alpha_{\text{\tiny{GW}}} \approx .878567$ denotes the approximation ratio achieved by the algorithm of Goemans and Williamson in [J. Assoc. Comput. Mach., 42 (1995), pp. 1115–1145]. This implies that if the Unique Games Conjecture of Khot in [Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] holds, then the Goemans–Williamson approximation algorithm is optimal. Our result indicates that the geometric nature of the Goemans–Williamson algorithm might be intrinsic to the MAX‐CUT problem. Our reduction relies on a theorem we call Majority Is Stablest. This was introduced as a conjecture in the original version of this paper, and was subsequently confirmed in [E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21–30]. A stronger version of this conjecture called Plurality Is Stablest is still open, although [E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21–30] contains a proof of an asymptotic version of it. Our techniques extend to several other two‐variable constraint satisfaction problems. In particular, subject to the Unique Games Conjecture, we show tight or nearly tight hardness results for MAX‐2SAT, MAX‐q‐CUT, and MAX‐2LIN(q). For MAX‐2SAT we show approximation hardness up to a factor of roughly $.943$. This nearly matches the $.940$ approximation algorithm of Lewin, Livnat, and Zwick in [Proceedings of the 9th Annual Conference on Integer Programming and Combinatorial Optimization, Springer‐Verlag, Berlin, 2002, pp. 67–82]. Furthermore, we show that our .943... factor is actually tight for a slightly restricted version of MAX‐2SAT. For MAX‐q‐CUT we show a hardness factor which asymptotically (for large q) matches the approximation factor achieved by Frieze and Jerrum [Improved approximation algorithms for MAX k‐CUT and MAX BISECTION, in Integer Programming and Combinatorial Optimization, Springer‐Verlag, Berlin, pp. 1–13], namely $1 - 1/q + 2({\rm ln}\,q)/q^2$. For MAX‐2LIN(q) we show hardness of distinguishing between instances which are $(1-\epsilon)$‐satisfiable and those which are not even, roughly, $(q^{-\epsilon/2})$‐satisfiable. These parameters almost match those achieved by the recent algorithm of Charikar, Makarychev, and Makarychev [Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 205–214]. The hardness result holds even for instances in which all equations are of the form $x_i - x_j = c$. At a more qualitative level, this result also implies that $1-\epsilon$ vs. ε hardness for MAX‐2LIN(q) is equivalent to the Unique Games Conjecture.

We give an algorithm that learns any monotone Boolean function $\fisafunc$ to any constant accuracy, under the uniform distribution, in time polynomial in n and in the decision tree size of $f.$ This is the first algorithm that can learn arbitrary monotone Boolean functions to high accuracy, using random examples only, in time polynomial in a reasonable measure of the complexity of $f.$ A key ingredient of the result is a new bound showing that the average sensitivity of any monotone function computed by a decision tree of size s must be at most $\sqrt{\log s}$. This bound has proved to be of independent utility in the study of decision tree complexity [O. Schramm, R. O'Donnell, M. Saks, and R. Servedio, Every decision tree has an influential variable, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 31–39]. We generalize the basic inequality and learning result described above in various ways—specifically, to partition size (a stronger complexity measure than decision tree size), p-biased measures over the Boolean cube (rather than just the uniform distribution), and real-valued (rather than just Boolean-valued) functions.

We give an algorithm that learns any monotone Boolean function f: {-1, 1}nrarr {-1, 1} to any constant accuracy, under the uniform distribution, in time polynomial in n and in the decision tree size of f. This is the first algorithm that can learn arbitrary monotone Boolean functions to high accuracy, using random examples only, in time polynomial in a reasonable measure of the complexity of f. A key ingredient of the result is a new bound showing that the average sensitivity of any monotone function computed by a decision tree of size s must be at most radic(log s). This bound has already proved to be of independent utility in the study of decision tree complexity (Schramm et al., 2005). We generalize the basic inequality and learning result described above in various ways; specifically, to partition size (a stronger complexity measure than decision tree size), p-biased measures over the Boolean cube (rather than just the uniform distribution), and real-valued (rather than just Boolean-valued) functions

Given a graph with maximum cut of (fractional) size c, the Goemans-Williamson semidefinite programming (SDP) algorithm by M. Goemans and D. Williamson (1995) is guaranteed to find a cut of size .878 middot c. However this guarantee becomes trivial when c is near frac12, since a random cut has expected size frac12. Recently, M. Charikar and K. Worth (2004) (analyzing an algorithm of U. Feige and G. Langberg (2001)) showed that given a graph with maximum cut frac12 + epsiv, one can find a cut of size frac12 + Omega(epsiv/ log(1/epsiv)). The main contribution of our paper is twofold: 1. We give a natural frac12 + epsiv vs. frac12 + O(epsiv/ log(1/epsiv)) SDP gap for MAXCUT in Gaussian space. This shows that the SDP-rounding algorithm of Charikar-Worth is essentially best possible. Further, the "s-linear rounding functions" used in the works of M. Charikar and K. Worth (2004) and U. Freige and M. Langberg (2001) arise as optimizers in our analysis, somewhat confirming a suggestion of U. Freige and M. Langberg (2001). 2. We show how this SDP gap can be translated into a long code test with the same parameters. This implies that beating the Charikar-Worth guarantee with any efficient algorithm is NP-hard, assuming the unique games conjecture (UGC) by S. Khot (2002). We view this result as essentially settling the approximability of MAXCUT, assuming UGC. Building on (1) we show how "randomness reduction" on related SDP gaps for the QUADRATICPROGRAMMING programming problem lets us make the Omega(log(1/epsiv)) gap as large as Omega(log n) for n-vertex graphs. In addition to optimally answering an open question of N. Alen et al. (2006), this technique may prove useful for other SDP gap problems. Finally, illustrating the generality of our technique in (2), we also show how to translate Reeds's SDP gap by J. Reeds (1993) for the Grothendieck Inequality into a UGC-hardness result for computing the par middot parinfin rarr 1norm of a matrix

A theorem of Bourgain [4] on Fourier tails states that if f :(-1, 1)n → (-1, 1) is a boolean-valued function on the discrete cube such that for any k > 0, [Σ|S| > k f(S)2 < k-1/2 + o(1), ] then essentially, f depends on only 2O(k) coordinates. This and related theorems such as Friedgut's Theorem [12], KKL [16], the FKN Theorem [14], and the Majority Is Stablest Theorem [27] have proven useful for numerous results in theoretical computer science [3, 5, 9, 6, 7, 10, 11, 18, 19, 20, 24, 17, 25, 23, 22, 28, 29, 31].In this paper we prove an analogue to Bourgain's Theorem for bounded functions on the discrete cube, f : (n ⋺ [-1,1]); such functions arise naturally in hardness-of-approximation problems, as averages of boolean functions. Specifically, we show that for every k > 0, if [Σ|S| > k f(S)2 < exp(-O(k2 log k))] then essentially, f depends on only 2O(k) coordinates. We also show, perhaps surprisingly, that this result is sharp up to the log k factor in the exponent.Our proof uses Fourier analysis, as well as some extremal properties of the Chebyshev polynomials.

In this paper, we study functions with low influences on product probability spaces. The analysis of Boolean functions f {-1, 1}/sup n/ /spl rarr/ {-1, 1} with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics. We prove an invariance principle for multilinear polynomials with low influences and bounded degree; it shows that under mild conditions the distribution of such polynomials is essentially invariant for all product spaces. Ours is one of the very few known non-linear invariance principles. It has the advantage that its proof is simple and that the error bounds are explicit. We also show that the assumption of bounded degree can be eliminated if the polynomials are slightly "smoothed"; this extension is essential for our applications to "noise stability "-type problems. In particular; as applications of the invariance principle we prove two conjectures: the "Majority Is Stablest" conjecture [29] from theoretical computer science, which was the original motivation for this work, and the "It Ain't Over Till It's Over" conjecture [27] from social choice theory. The "Majority Is Stablest" conjecture and its generalizations proven here, in conjunction with the "Unique Games Conjecture" and its variants, imply a number of (optimal) inapproximability results for graph problems.

We prove that for any decision tree calculating a Boolean function f : {-1,1}/sup n/ /spl rarr/ {-1, 1}, Var[f] /spl les/ /spl Sigma/ /sub i=1/ /sup n/ /spl delta//sup i/Inf/sub i/(f), i = 1 where /spl delta//sup i/ is the probability that the ith input variable is read and Inf/sub i/(f) is the influence of the ith variable on f. The variance, influence and probability are taken with respect to an arbitrary product measure on {-1, 1}/sup n/n. It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced Boolean function with a decision tree of depth d has a variable with influence at least 1/d. The only previous nontrivial lower bound known was /spl Omega/(d2/sup -d/). Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with nonBoolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least/spl Omega/(v/sup 4/3//p/sup 1/3/), where v is the number of vertices and p /spl les/ 1/2 is the critical threshold probability. This supersedes the milestone /spl Omega/(v/sup 4/3//p/sup 1/3/) bound of Hajnal (1991) and is sometimes superior to the best known lower bounds of Chakrabarti-Khot (2001) and Friedgut-Kahn-Wigderson (2002).

We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. (1994). We give a poly(n//spl epsi/) time algorithm for learning a mixture of k arbitrary product distributions over the n-dimensional Boolean cube {0, 1}/sup n/ to accuracy /spl epsi/, for any constant k. Previous poly(n)-time algorithms could only achieve this for k = 2 product distributions; our result answers an open question stated independently in M. Cryan (1999) and Y. Freund and Y. Mansour (1999). We further give evidence that no polynomial time algorithm can succeed when k is superconstant, by reduction from a notorious open problem in PAC learning. Finally, we generalize our poly(n//spl epsi/) time algorithm to learn any mixture of k = O(1) product distributions over {0, 1,... , b }/sup n/,for any b = O(1).

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of /spl alpha//sub cw/+ /spl epsi/, for all /spl epsi/ > 0, where /spl alpha//sub cw/ denotes the approximation ratio achieved by the Goemans-Williamson algorithm (1995). /spl alpha//sub cw/ /spl ap/ .878567. This result is conditional, relying on two conjectures: a) the unique games conjecture of Khot; and, b) a very believable conjecture we call the majority is stablest conjecture. These results indicate that the geometric nature of the Goemans-Williamson algorithm might be intrinsic to the MAX-CUT problem. The same two conjectures also imply that it is NP-hard to (/spl beta/ + /spl epsi/)-approximate MAX-2SAT, where /spl beta/ /spl ap/ .943943 is the minimum of (2 + (2//spl pi/) /spl theta/)/(3 - cos(/spl theta/)) on (/spl pi//2, /spl pi/). Motivated by our proof techniques, we show that if the MAX-2CSP and MAX-2SAT problems are slightly restricted - in a way that seems to retain all their hardness -then they have (/spl alpha//sub GW/-/spl epsi/)- and (/spl beta/ - /spl epsi/)-approximation algorithms, respectively. Though we are unable to prove the majority is stablest conjecture, we give some partial results and indicate possible directions of attack. Our partial results are enough to imply that MAX-CUT is hard to (3/4 + 1/(2/spl pi/) + /spl epsi/)-approximate (/spl ap/ .909155), assuming only the unique games conjecture. We also discuss MAX-2CSP problems over non-Boolean domains and state some related results and conjectures. We show, for example, that the unique games conjecture implies that it is hard to approximate MAX-2LIN(q) to within any constant factor.

We give new extremal bounds on polynomial threshold function (PTF) representations of Boolean functions. Our results include the following: 1) Almost every Boolean function has PTF degree at most n/2+O(/spl radic/(n log n)). Together with results of Anthony and Alon, we establish a conjecture of Wang and Williams [1991] and Aspnes, Beigel, Furst, and Rudich [1994] up to lower order terms. 2) Every Boolean function has PTF density at most (1-1/O(n))2/sup n/. This improves a result of Gotsman [1989]. 3) Every Boolean function has weak PTF density at most O(1)2/sup n/. This gives a negative answer to a question posed by Saks [1993]. 4) PTF degree /spl lfloor/log/sub 2/m/spl rfloor/+1 is necessary and sufficient for Boolean functions with sparsity m. This answers a question of Beigel [2000].

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1}/sup n/. We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for learning these classes in a natural passive learning model where the learner has no influence over the choice of examples used for learning.

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for learning such functions from uniform random examples which runs in time roughly (nk)ω/(ω + 1), where ω < 2.376 is the matrix multiplication exponent. We thus obtain the first polynomial factor improvement on the naive nk time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.

We give new upper and lower bounds on the degree of real multivariate polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.

We investigate whether, if NP is slightly hard on average, it is very hard on average.

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution to within any constant error parameter. We also give the first quasipolynomial time algorithm for learning any function of a polylog number of polynomial-weight halfspaces under any distribution. As special cases of these results we obtain algorithms for learning intersections and thresholds of halfspaces. Our uniform distribution learning algorithms involve a novel non-geometric approach to learning halfspaces; we use Fourier techniques together with a careful analysis of the noise sensitivity of functions of halfspaces. Our algorithms for learning under any distribution use techniques from real approximation theory to construct low degree polynomial threshold functions.

(MATH) In this paper we investigate the following question: If $\np$ is slightly hard on average, is it very hard on average? We show the answer is yes; if there is a function in $\np$ which is \mbox{$(1-1/\poly(n))$}-hard for circuits of polynomial size, then there is a function in $\np$ which is $(\half + n^{-1/2 + \epsilon})$-hard for circuits of polynomial size. Our proof technique is to generalize the Yao XOR Lemma, allowing us to characterize nearly tightly the hardness of a composite function \linebreak $g(f(x_1), \ldots, f(x_n))$, in terms of: (i) the original hardness of $f$, and (ii) the {\em expected bias} of the function $g$ when subjected to random restrictions. The computational result we prove essentially matches an information-theoretic bound.