We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine based on the sum-of-squares method that finds a low-dimensional separation-preserving projection of the input data. Our method provides a non-spherical analog of the classical dimension reduction based on singular value decomposition that, among several other applications, forms a key component of the celebrated spherical clustering algorithm of Vempala and Wang (2004). As applications, we obtain an algorithm to (1) cluster an arbitrary total-variation separated mixture of $k$ centered (i.e., zero-mean) Gaussians with $n\geq \mathrm{poly}(d) f(w_{\min}^{-1})$ samples and $\mathrm{poly}(n)$ time, and (2) cluster an arbitrary total-variation separated mixture of $k$ Gaussians with identical but arbitrary unknown covariance with $n \geq d^{O(\log w_{\min}^{-1})} f(w_{\min}^{-1})$ samples and $n^{O(\log w_{\min}^{-1})}$ time. Here, $w_{\min}$ is the minimum mixing weight of the input mixture, and $f$ does not depend on the dimension $d$. Our algorithms naturally extend to tolerate a dimension-independent fraction of arbitrary outliers. Before this work, the techniques in the state-of-the-art non-spherical clustering algorithms needed $d^{O(k)} f(w_{\min}^{-1})$ samples and time for clustering such mixtures. Our results may come as a surprise in the context of the $d^{\Omega(k)}$ statistical query and sum-of-squares lower bounds (Diakonikolas et al. (2017, 2024)) for clustering non-spherical Gaussian mixtures. While these results are usually thought to rule out $d^{o(k)}$ cost algorithms for the problem, our results show that the lower bounds can, in fact, be circumvented for a remarkably general class of Gaussian mixtures.

In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices \(\mathcal{A}=\{A_1,A_2,\ldots,A_r\}\subseteq \mathbb{R}^{n\times n}\), given any subset \(T\subseteq [r]\), our goal is to find sparse weights \(\mu_i\in\mathbb{R}_{\ge 0}\) such that \((1-\varepsilon)\sum_{i\in T} A_i \;\preceq\; \sum_{i\in T} \mu_i A_i \;\preceq\; (1+\varepsilon)\sum_{i\in T} A_i\). This generalizes spectral sparsification of graphs which corresponds to \(\mathcal{A}\) being the set of Laplacians of edges. It also captures sparsifying Cayley graphs by choosing a subset of generators. The former has been extensively studied with optimal sparsifiers known. The latter has received attention recently and was solved for a few special groups (e.g., \(\mathbb{F}_2^n\)). Prior work shows any sum of PSD matrices can be sparsified down to \(O(n)\) elements. This bound however turns out to be too coarse and in particular yields no non-trivial bound for building Cayley sparsifiers for Cayley graphs. In this work, we develop a new, instance-specific (i.e., specific to a given collection \(\mathcal{A}\)) theory of PSD matrix sparsification based on a new parameter \(N^*(\mathcal{A})\) which we call connectivity threshold that generalizes the threshold of the number of edges required to make a graph connected. Our main result gives a sparsifier that uses at most \(O(\varepsilon^{-2} N^*(\mathcal{A}) (\log n) (\log r))\) matrices and is constructible in randomized polynomial time. We also show that we need \(N^*(\mathcal{A})\) elements to sparsify for any \(\varepsilon \lt 0.99\). As the main application of our framework, we prove that any Cayley graph can be sparsified to \(O(\varepsilon^{-2}\log^4 N)\) generators. Previously, a non-trivial bound on Cayley sparsifiers was known only in the case when the group is \(\mathbb{F}_2^n\).

In this work, we revisit algorithms for Tensor PCA: given an order-\(r\) tensor of the form \(T = G + \lambda \cdot v^{\otimes r}\) where \(G\) is a random symmetric Gaussian tensor with unit variance entries and \(v\) is an unknown boolean vector in \(\{\pm 1\}^n\), what's the minimum \(\lambda\) at which one can distinguish \(T\) from a random Gaussian tensor and more generally, recover \(v\)? As a result of a long line of work, we know that for any \(\ell \in \mathbb{N}\), there is a \(n^{O(\ell)}\) time algorithm that succeeds when the signal strength \(\lambda \gtrsim \sqrt{\log n} \cdot n^{-r/4} \cdot \ell^{1/2 - r/4}\). The question of whether the logarithmic factor is necessary turns out to be crucial to understanding whether larger polynomial time allows recovering the signal at a lower signal strength. Such a smooth trade-off is necessary for tensor PCA being a candidate problem for quantum speedups. It was first conjectured and then, more recently, with an eye on smooth trade-offs, reiterated in a blogpost of Bandeira.

We revisit the question of whether it is possible to build succinct non-interactive arguments (SNARGs) for all of NP under standard assumptions using non-signaling probabilistically checkable proofs [Kalai-Raz-Rothblum, STOC’ 14]. In particular, we observe that using exponential-length PCPs appears to circumvent all of the existing barriers.

Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such results rely on the hypothesis that if the low-degree moments of the planted and null distributions are sufficiently close, then no efficient (noise-tolerant) algorithm should be able to distinguish between them. This hypothesis is appealing due to the simplicity of calculating the low-degree likelihood ratio (LDLR), a quantity that measures the similarity between low-degree moments. However, despite sustained interest in the area, it remains unclear whether low-degree indistinguishability actually rules out any interesting class of algorithms.

In this work, we give a poly(d,k) time and sample algorithm for efficiently learning the parameters (i.e., the means and the mixture weights) of a mixture of k spherical distributions in d dimensions. Unlike all previous methods, our techniques apply to heavy-tailed distributions and include examples that do not even have finite covariances. Our method succeeds whenever the component distributions have a characteristic function with sufficiently heavy tails. Examples of such distributions include the Laplace distribution and uniform over [−1, 1] but crucially exclude Gaussians.

We give a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in ℝ d , for any fixed k , in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient partial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.

We prove that for every odd q ⩾ 3, any q-query binary, possibly non-linear locally decodable code (q-LDC) E : {±1}k→ {±1}nmust satisfy k ⩽ Õ(n1−2/q). For even q, this bound was established in a sequence of works [KT00], [GKST06], [KW04]. For q = 3, the above bound was achieved in a recent work [AGKM23] using an argument that crucially exploits known exponential lower bounds for 2-LDCs. Their strategy hits an inherent bottleneck for q ⩾ 5.Our key insight is identifying a general sufficient condition on the hypergraph of local decoding sets called t-approximate strong regularity. This condition demands that 1) the number of hyperedges containing any given subset of vertices of size t (i.e., its co-degree) be equal to the same but arbitrary value dtup to a multiplicative constant slack, and 2) all other co-degrees be upper-bounded relative to dt. This condition significantly generalizes related proposals in prior works [GKM22], [HKM23], [AGKM23], [HKM+24] that demand absolute upper bounds on all co-degrees.We give an argument based on spectral bounds on Kikuchi Matrices that lower bounds the blocklength of any LDC whose local decoding sets satisfy t-approximate strong regularity for any t ⩽ q. Crucially, unlike prior works, our argument works despite having no non-trivial absolute upper bound on the co-degrees of any set of vertices. To apply our argument to arbitrary q-LDCs, we give a new, greedy, approximate strong regularity decomposition that shows that arbitrary, dense enough hypergraphs can be partitioned (up to a small error) into approximately strongly regular pieces satisfying the required relative bounds on the co-degrees.

There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) — a quantitative estimate of the closeness of low-degree moments — between a null distribution and a related planted distribution. Such hardness results are now ubiquitous not only for foundational average-case problems but also central questions in statistics and cryptography. This line of work is supported by the low-degree conjecture of Hopkins [1], which postulates that a vanishing degree-D LDA implies the absence of any noise-tolerant distinguishing algorithm with runtime ${n^{\tilde {\mathcal{O}}(D)}}$ whenever 1) the null distribution is product on ${\{ 0,1\} ^{\binom{n}{k}}}$, and 2) the planted distribution is permutation invariant, that is, invariant under any relabeling [n] → [n].In this paper, we disprove this conjecture. Specifically, we show that for any fixed ε > 0 and k ⩾ 2, there is a permutation-invariant planted distribution on ${\{ 0,1\} ^{\binom{n}{k}}}$ that has a vanishing degree-n1−O(ε)LDA with respect to the uniform distribution on ${\{ 0,1\} ^{\binom{n}{k}}}$, yet the corresponding ε-noisy distinguishing problem can be solved in ${n^{O\left( {{{\log }^{1/(k - 1)}}(n)} \right)}}$ time. Our construction relies on algorithms for list-decoding for noisy polynomial interpolation in the high-error regime.We also give another construction of a pair of planted and (non-product) null distributions on ℝn×nwith a vanishing nΩ(1)-degree LDA while the largest eigenvalue serves as an efficient noise-tolerant distinguisher.Our results suggest that while a vanishing LDA may still be interpreted as evidence of hardness, developing a theory of average-case complexity based on such heuristics requires a more careful approach.

Motivated by connections between algebraic complexity lower bounds and tensor decompositions, we investigate Koszul-Young flattenings, which are the main ingredient in recent lower bounds for matrix multiplication. Based on this tool we give a new algorithm for decomposing an $n_{1} \times n_{2} \times n_{3}$ tensor as the sum of a minimal number of rank-1 terms, and certifying uniqueness of this decomposition. For $n_{1} \leq n_{2} \leq n_{3}$ with $n_{1} \rightarrow \infty$ and $n_{3} / n_{2}=O(1)$, our algorithm is guaranteed to succeed when the tensor rank is bounded by $r \leq(1-\epsilon)\left(n_{2}+n_{3}\right)$ for an arbitrary $\epsilon \gt 0$, provided the tensor components are generically chosen. For any fixed $\epsilon$, the runtime is polynomial in $n_{3}$. When $n_{2}=n_{3}=n$, our condition on the rank gives a factor-of- 2 improvement over the classical simultaneous diagonalization algorithm, which requires $r \leq n$, and also improves on the recent algorithm of Koiran (2024) which requires $r \leq 4 n / 3$. It also improves on the PhD thesis of Persu (2018) which solves rank detection for $r \leq 3 n / 2$. We complement our upper bounds by showing limitations, in particular that no flattening of the style we consider can surpass rank $n_{2}+n_{3}$. Furthermore, for $n \times n \times n$ tensors, we show that an even more general class of degree- $\boldsymbol{d}$ polynomial flattenings cannot surpass rank Cn for a constant $C=C(d)$. This suggests that for tensor decompositions, the case of generic components may be fundamentally harder than that of random components, where efficient decomposition is possible even in highly overcomplete settings.

A set of high dimensional points X$= \{x_{1},x_{2},\ldots,x_{n}\}\subseteq \mathbb{R}^{d}$in isotropic position is said to be$\delta$-anti concentrated if for every direction$v$, the fraction of points in$X$satisfying$\left|\left\langle x_i, v\right\rangle\right| \leqslant \delta$is at most$O(\delta)$. Motivated by applications to list-decodable learning and clustering, three recent works [7], [44], [71] considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points X corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures. Unlike related efficient certificates of concentration properties that are known for wide class of distri-butions [52], the aforementioned approach has been limited only to rotationally invariant distributions (and their affine transformations) with the only prominent example being Gaussian distributions. This work presents a new (and arguably the most natural) formulation for anti- concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over$L_{p}$balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e.g., list-decodable learning and clustering, to such distributions. As in the case of previous works, our certificates are also obtained via relaxations in the sum-of-squares hierarchy. However, the nature of our argument differs significantly from prior works that formulate anti-concentration as the non-negativity of an explicit polynomial. Our argument constructs a canonical integer program for anti-concentration and analysis a SoS relaxation of it, independent of the intended application. The explicit polynomials appearing in prior works can be seen as specific dual certificates to this program. From a technical standpoint, unlike existing works that explicitly construct sum-of-squares certificates, our argument relies on duality and analyzes a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions.

We give a simple, greedy$O(n^{\omega+0.5})=O(n^{2.872})$- time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01) that succeeds whenever the size of the planted clique is$k\geq O(\sqrt{n}\log^{2}n)$. In the model, the edges touching the vertices in the planted k-clique are drawn independently with probability$p=1/2$while the edges not touching the planted clique are chosen by an adversary in response to the random choices. Our result shows that the computational threshold in the semirandom setting is within a$O(\log^{2}n)$factor of the information-theoretic one [Ste17] thus resolving an open question of Steinhardt. This threshold also essentially matches the conjectured computational threshold for the well-studied special case of fully random planted clique. All previous algorithms [CSV17], [MMT20], [BKS23] in this model are based on rather sophisticated rounding algorithms for entropy-constrained semidefinite programming relaxations and their sum-of-squares strengthenings and the best known guarantee is a$n^{O(1/\varepsilon}$) -time algorithm to list-decode planted cliques of size$k\geq\tilde{O}(n^{1/2+\varepsilon})$. In particular, the guarantee trivializes to quasi-polynomial time if the planted clique is of size$O (\sqrt{n}$poly log$n$). Our algorithm achieves an almost optimal guarantee with a surprisingly simple greedy algorithm. The prior state-of-the-art algorithmic result above is based on a reduction to certifying bounds on the size of unbalanced bicliques in random graphs - closely related to certifying the restricted isometry property (RIP) of certain random matrices and known to be hard in the low-degree polynomial model. Our key idea is a new approach that relies on the truth of - but not efficient certificates for - RIP of a new class of matrices built from the input graphs.

We give improved lower bounds for binary 3-query locally correctable codes (3-LCCs)$C: \{\ 0,1 \}^k \rightarrow \{\ 0,1 \}^n$. Specifically, we prove: 1) If C is a linear design 3-LCC, then$n \geq 2^{(1 - o(1))\sqrt{k} }$. A design 3-LCC has the additional property that the correcting sets for every codeword bit form a perfect matching, and every pair of codeword bits is queried an equal number of times across all matchings. Our bound is tight up to a factor$\sqrt{8}$in the exponent of 2, as the best construction of binary 3-LCCs (obtained by taking Reed--Muller codes on F_4 and applying a natural projection map) is a design 3-LCC with$n \leq 2^{\sqrt{8 k}}$. Up to a factor of 8, this resolves the Hamada conjecture on the maximum F_2-codimension of a 4-design. 2) If C is a smooth, non-linear, adaptive 3-LCC with perfect completeness, then,$n \geq 2^{\Omega(k^{1/5})}$. 3) If C is a smooth, non-linear, adaptive 3-LCC with completeness 1 - \eps, then n \geq \Omega(k^{\frac${1}{2\eps}}). In particular, when$\eps$is a small constant, this implies a lower bound for general non-linear LCCs that beats the prior best$n \geq \Omega(k^3)$lower bound of Alrabiah-Guruswami-Kothari-Manohar by a polynomial factor. Our design LCC lower bound is obtained via a fine-grained analysis of the Kikuchi matrix method applied to a variant of the matrix used in the work of Kothari and Manohar (2023). Our lower bounds for non-linear codes are obtained by designing a from-scratch reduction from nonlinear 3-LCCs to a system of “chain XOR equations” — polynomial equations with a similar structure to the long chain derivations that arise in the lower bounds for linear 3-LCCs of Kothari and Manohar.

We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the n-dimensional hypercube. In both cases, the resulting algorithms yield a multiplicative approximation in 2O(k) poly(n) time. In particular, we obtain a approximation in polynomial time. For the unit sphere, this improves on the rounding algorithms of [5] that need quasi-polynomial time to obtain a similar approximation guarantee. Over the n-dimensional hypercube, our results match the guarantee of a search algorithm of Khot and Naor [19] that obtains a similar approximation ratio via techniques from convex geometry. Unlike their method, our algorithm obtains an upper bound on the integrality gap of SDP relaxations for the problem and as a result, also yields a certificate on the optimum value of the input instance. Our results naturally generalize to homogeneous polynomials of higher degree and imply improved algorithms for approximating satisfiable instances of Max-3SAT.

We prove that the blocklength n of a linear 3-query locally correctable code (LCC) L ∶ Fk → Fn with distance δ must be at least n ≥ 2Ω((δ2 k/(|F|−1)2)1/8). In particular, the blocklength of a linear 3-query LCC with constant distance over any small field grows exponentially with k. This improves on the best prior lower bound of n ≥ Ω(k3), which holds even for the weaker setting of 3-query locally decodable codes (LDCs), and comes close to matching the best-known construction of 3-query LCCs based on binary Reed–Muller codes, which achieve n ≤ 2O(k1/2). Because there is a 3-query LDC with a strictly subexponential blocklength, as a corollary we obtain the first strong separation between q-query LCCs and LDCs for any constant ‍q ≥ 3. Our proof is based on a new upgrade of the method of spectral refutations via Kikuchi matrices developed in recent works that reduces establishing (non-)existence of combinatorial objects to proving unsatisfiability of associated XOR instances. Our key conceptual idea is to apply this method with XOR instances obtained via long-chain derivations — a structured variant of low-width resolution for XOR formulas from proof complexity.

We prove that for every D ∈ N, and large enough constant d ∈ N, with high probability over the choice of G ∼ G(n,d/n), the Erdos-Renyi random graph distribution, the canonical degree 2D Sum-of-Squares relaxation fails to certify that the largest independent set in G is of size o(n/√d D4). In particular, degree D sum-of-squares strengthening can reduce the integrality gap of the classical theta SDP relaxation by at most a O(D4) factor. This is the first lower bound for >4-degree Sum-of-Squares (SoS) relaxation for any problems on ultra sparse random graphs (i.e. average degree of an absolute constant). Such ultra-sparse graphs were a known barrier for previous methods and explicitly identified as a major open direction. Indeed, the only other example of an SoS lower bound on ultra-sparse random graphs was a degree-4 lower bound for Max-Cut. Our main technical result is a new method to obtain spectral norm estimates on graph matrices (a class of low-degree matrix-valued polynomials in G(n,d/n)) that are accurate to within an absolute constant factor. All prior works lose log n factors that trivialize any lower bound on o(logn)-degree random graphs. We combine these new bounds with several upgrades on the machinery for analyzing lower-bound witnesses constructed by pseudo-calibration so that our analysis does not lose any ω(1)-factors that would trivialize our results. In addition to other SoS lower bounds, we believe that our methods for establishing spectral norm estimates on graph matrices will be useful in the analyses of numerical algorithms on average-case inputs.

We study the computational complexity of two related problems: recovering a planted q-coloring in G(n,1/2), and finding efficiently verifiable witnesses of non-q-colorability (a.k.a. refutations) in G(n,1/2). Our main results show hardness for both these problems in a restricted-but-powerful class of algorithms based on computing low-degree polynomials in the inputs.The problem of recovering a planted q-coloring is equivalent to recovering q disjoint planted cliques that cover all the vertices — a potentially easier variant of the well-studied planted clique problem. Our first result shows that this variant is as hard as the original planted clique problem in the low-degree polynomial model of computation: each clique needs to have size k >> sqrt(n) for efficient recovery to be possible. For the related variant where the cliques cover a (1-epsilon)-fraction of the vertices, we also show hardness by reduction from planted clique.Our second result shows that refuting q-colorability of G(n,1/2) is hard in the low-degree polynomial model when q >> n^{2/3} but easy when q << n^{1/2}, and we leave closing this gap for future work. Our proof is more subtle than similar results for planted clique and involves constructing a non-standard distribution over q-colorable graphs. We note that while related to several prior works, this is the first work that explicitly formulates refutation problems in the low-degree polynomial model.The proofs of our main results involve showing low-degree hardness of hypothesis testing between an appropriately constructed pair of distributions. For refutation, we show completeness of this approach: in the low-degree model, the refutation task is precisely as hard as the hardest associated testing problem, i.e., proving hardness of refutation amounts to finding a "hard" distribution.

We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst case and average case input models, where the input is generated by (1) choosing an arbitrary planted assignment $x^{*}$, (2) choosing an arbitrary clause structure, and (3) choosing literal negations for each clause from an arbitrary distribution “shifted by $x^{*}$” so that $x^{*}$ satisfies each constraint. For an n variable semirandom planted instance of a k-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but a $o(1)$-fraction of constraints, provided that the instance has at least $\tilde{O}\left(n^{k / 2}\right)$ constraints. This matches, up to ${\mathrm {polylog}} (n)$ factors, the clause threshold for algorithms that solve fully random planted CSPs [23], as well as algorithms that refute random and semirandom CSPs [1], [4]. Our result shows that despite having worst case clause structure, the randomness in the literal patterns makes semirandom planted CSPs significantly easier than worst case, where analogous results require $O\left(n^{k}\right)$ constraints [7], [26]. Perhaps surprisingly, our algorithm follows a significantly different conceptual framework when compared to the recent resolution of semirandom CSP refutation. This turns out to be inherent and, at a technical level, can be attributed to the need for relative spectral approximation of certain random matrices — reminiscent of the classical spectral sparsification — which ensures that an SDP can certify the uniqueness of the planted assignment. In contrast, in the refutation setting, it suffices to obtain a weaker guarantee of absolute upper bounds on the spectral norm of related matrices.

We present a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, an important and well-studied setting for independent component analysis (ICA). Specifically, given an $\varepsilon$-corrupted sample from a distribution D obtained by applying an unknown affine transformation $x \rightarrow A x+b$ to the uniform distribution on a d-dimensional hypercube $[-1,1]^{d}$, our algorithm constructs $\widehat{A}, \hat{b}$ such that the total variation distance of the distribution $\widehat{D}$ from D is $O(\varepsilon)$ using poly $(d)$ time and samples. Total variation distance is the information-theoretically strongest possible notion of distance in our setting and our recovery guarantees in this distance are optimal up to the absolute constant factor multiplying $\varepsilon$. In particular, if the rows of A are normalized to be unit length, our total variation distance guarantee implies a bound on the sum of the $\ell_{2}$ distances between the row vectors of A and $A^{\prime}, \sum_{i=1}^{d}\left\|a_{(i)}-\hat{a}_{(i)}\right\|_{2}=O(\varepsilon)$. In contrast, the strongest known prior results only yield an $\varepsilon^{O(1)}$ (relative) bound on the distance between individual $a_{i}$’s and their estimates and translate into an $O\left(d \varepsilon^{O(1)}\right)$ bound on the total variation distance.Prior algorithms for this problem rely on implementing standard approaches [12] for ICA based on the classical method of moments [18], [32] combined with robust moment estimators. We prove that any approach that relies on method of moments must provably fail to obtain a dimension independent bound on the total error $\sum_{i}\left\|a_{(i)}-\hat{a}_{(i)}\right\|_{2}$ (and consequently, also in total variation distance). Our key innovation is a new approach to ICA (even to outlier-free ICA) that circumvents the difficulties in the classical method of moments and instead relies on a new geometric certificate of correctness of an affine transformation. Our algorithm, Robust Gradient Descent, is based on a new method that iteratively improves its estimate of the unknown affine transformation whenever the requirements of the certificate are not met.

In this note, we describe a $α_{GW} + \tildeΩ(1/d^2)$-factor approximation algorithm for Max-Cut on weighted graphs of degree $\leq d$. Here, $α_{GW}\approx 0.878$ is the worst-case approximation ratio of the Goemans-Williamson rounding for Max-Cut. This improves on previous results for unweighted graphs by Feige, Karpinski, and Langberg and Florén. Our guarantee is obtained by a tighter analysis of the solution obtained by applying a natural local improvement procedure to the Goemans-Williamson rounding of the basic SDP strengthened with triangle inequalities.

The hypergraph Moore bound characterizes the extremal trade-off between the girth — the number of hyperedges in the smallest cycle or even cover (a subhypergraph with all degrees even) and size — the number of hyperedges in a hypergraph. For graphs, a bound tight up to the leading constant was proven in a classical work of Alon, Hoory and Linial [3]. For hypergraphs of uniformity k > 2, an appropriate generalization was conjectured by Feige [14]. The conjecture was settled up to an additional log4k+1 n factor in the size in a recent work of Guruswami, Kothari and Manohar [16]. Their argument relies on a connection between the existence of short even covers and the spectrum of a certain randomly signed Kikuchi matrix. Their analysis, especially for the case of odd k, is significantly complicated. In this work, we present a substantially simpler and shorter proof of the hypergraph Moore bound. Our key idea is the use of a new reweighted Kikuchi matrix and an edge deletion trick that allows us to drop several involved steps in [16]'s analysis such as combinatorial bucketing of rows of the Kikuchi matrix and the use of the Schudy-Sviridenko polynomial concentration. Our simpler proof also obtains tighter parameters: in particular, the argument gives a new proof of the classical Moore bound of [3] with no loss (the proof in [16] loses a log3n factor), and loses only a single logarithmic factor for all k > 2-uniform hypergraphs. As in [16], our ideas naturally extend to yield a simpler proof of the full trade-off for strongly refuting smoothed instances of constraint satisfaction problems with similarly improved parameters. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.10850

In this work, we give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on the dimension in the sample complexity.

A code C ∶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b ∈ {0,1}k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(ko(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k2/log(k)) on the blocklength.

We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian. The previous best algorithms for this model succeed if the planted clique has size at least n2/3 in a graph with n vertices. Our algorithms work for planted-clique sizes approaching n1/2 — the information-theoretic threshold in the semi-random model and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt.

A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of testable learning, where the goal is to replace hard-to-verify distributional assumptions (such as Gaussianity) with efficiently testable ones and to require that the learner succeed whenever the unknown distribution passes the corresponding test. In this model, they gave an efficient algorithm for learning halfspaces under testable assumptions that are provably satisfied by Gaussians.

In this work, we revisit the problem of estimating the mean and covariance of an unknown $d$-dimensional Gaussian distribution in the presence of an $\varepsilon$-fraction of adversarial outliers. The work of Diakonikolas et al. (2016) gave a polynomial time algorithm for this task with optimal $\tilde{O}(\varepsilon)$ error using $n = \textrm{poly}(d, 1/\varepsilon)$ samples. On the other hand, Kothari and Steurer (2017) introduced a general framework for robust moment estimation via a canonical sum-of-squares relaxation that succeeds for the more general class of \emph{certifiably subgaussian} and \emph{certifiably hypercontractive} (Bakshi and Kothari, 2020) distributions. When specialized to Gaussians, this algorithm obtains the same $\tilde{O}(\varepsilon)$ error guarantee as Diakonikolas et al. (2016) but incurs a super-polynomial sample complexity ($n = d^{O(\log 1/\varepsilon)}$) and running time ($n^{O(\log(1/\varepsilon))}$). This cost appears inherent to their analysis as it relies only on sum-of-squares certificates of upper bounds on directional moments while the analysis in Diakonikolas et al. (2016) relies on \emph{lower bounds} on directional moments inferred from algebraic relationships between moments of Gaussian distributions. We give a new, simple analysis of the \emph{same} canonical sum-of-squares relaxation used in Kothari and Steurer (2017) and Bakshi and Kothari (2020) and show that for Gaussian distributions, their algorithm achieves the same error, sample complexity and running time guarantees as of the specialized algorithm in Diakonikolas et al. (2016). Our key innovation is a new argument that allows using moment lower bounds without having sum-of-squares certificates for them. We believe that our proof technique will likely be useful in designing new robust estimation algorithms.

We give the first polynomial time and sample (epsilon, delta)-differentially private (DP) algorithm to estimate the mean, covariance and higher moments in the presence of a constant fraction of adversarial outliers. Our algorithm succeeds for families of distributions that satisfy two well-studied properties in prior works on robust estimation: certifiable subgaussianity of directional moments and certifiable hypercontractivity of degree 2 polynomials. Our recovery guarantees hold in the “right affine-invariant norms”: Mahalanobis distance for mean, multiplicative spectral and relative Frobenius distance guarantees for covariance and injective norms for higher moments. Prior works obtained private robust algorithms for mean estimation of subgaussian distributions with bounded covariance. For covariance estimation, ours is the first efficient algorithm (even in the absence of outliers) that succeeds without any condition-number assumptions. Our algorithms arise from a new framework that provides a general blueprint for modifying convex relaxations for robust estimation to satisfy strong worst-case stability guarantees in the appropriate parameter norms whenever the algorithms produce witnesses of correctness in their run. We verify such guarantees for a modification of standard sum-of-squares (SoS) semidefinite programming relaxations for robust estimation. Our privacy guarantees are obtained by combining stability guarantees with a new “estimate dependent” noise injection mechanism in which noise scales with the eigenvalues of the estimated covariance. We believe this framework will be useful more generally in obtaining DP counterparts of robust estimators. Independently of our work, Ashtiani and Liaw [AL21] also obtained a polynomial time and sample private robust estimation algorithm for Gaussian distributions.

We give efficient algorithms for finding power-sum decomposition of an input polynomial $P(x)=\displaystyle \sum_{i\leq m}p_{i}(x)^{d}$ with component $p_{i}s$. The case of linear $p_{i}s$ is equivalent to the well-studied tensor decomposition problem while the quadratic case occurs naturally in studying identifiability of non-spherical Gaussian mixtures from low-order moments. Unlike tensor decomposition, both the unique identifiability and algorithms for this problem are not well-understood. For the simplest setting of quadratic $p_{i}s$ and $d=3$, prior work of [11] yields an algorithm only when $m\leq\overline{O}(\sqrt{n})$. On the other hand, the more general recent result of [13] builds an algebraic approach to handle any $m=n^{O(1)}$ components but only when d is large enough (while yielding no bounds for d=3 or even d=100) and only handles an inverse exponential noise. Our results obtain a substantial quantitative improvement on both the prior works above even in the base case of d=3 and quadratic $p_{i}s$. Specifically, our algorithm succeeds in decomposing a sum of $m\sim\overline{O}(n)$ generic quadratic $p_{i}s$ for $d=3$ and more generally the dth power-sum of $m\sim n^{2d/15}$ generic degree-K polynomials for any K$\geq$2. Our algorithm relies only on basic numerical linear algebraic primitives, is exact (i.e., obtain arbitrarily tiny error up to numerical precision), and handles an inverse polynomial noise when the $p_{i}s$ have random Gaussian coefficients. Our main tool is a new method for extracting the linear span of $p_{i}s$ by studying the linear subspace of low-order partial derivatives of the input P. For establishing polynomial stability of our algorithm in average-case, we prove inverse polynomial bounds on the smallest singular value of certain correlated random matrices with low-degree polynomial entries that arise in our analyses. Since previous techniques only yield significantly weaker bounds, we analyze the smallest singular value of matrices by studying the largest singular value of certain deviation matrices via graph matrix decomposition and the trace moment method.

Strategic behavior is a fundamental problem in a variety of real-world applications that require some form of peer assessment, such as peer grading of homeworks, grant proposal review, conference peer review of scientific papers, and peer assessment of employees in organizations. Since an individual's own work is in competition with the submissions they are evaluating, they may provide dishonest evaluations to increase the relative standing of their own submission. This issue is typically addressed by partitioning the individuals and assigning them to evaluate the work of only those from different subsets. Although this method ensures strategyproofness, each submission may require a different type of expertise for effective evaluation. In this paper, we focus on finding an assignment of evaluators to submissions that maximizes assigned evaluators' expertise subject to the constraint of strategyproofness. We analyze the price of strategyproofness: that is, the amount of compromise on the assigned evaluators' expertise required in order to get strategyproofness. We establish several polynomial-time algorithms for strategyproof assignment along with assignment-quality guarantees. Finally, we evaluate the methods on a dataset from conference peer review.

Consider a system of m polynomial equations {pi(x) = bi}i≤m of degree D ≥ 2 in n-dimensional variable x ∊ ℝn such that each coefficient of every pi and bis are chosen at random and independently from some continuous distribution. We study the basic question of determining the smallest m–the algorithmic threshold–for which efficient algorithms can find refutations (i.e. certificates of unsatisfiability) for such systems. This setting generalizes problems such as refuting random SAT instances, low-rank matrix sensing and certifying pseudo-randomness of Goldreich's candidate generators and generalizations. We show that for every d ∊ ℕ, the (n + m)O(d)-time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever . We prove a lower bound in the restricted low-degree polynomial model of computation which suggests that this trade-off between SoS degree and the number of equations is nearly tight for all d. We also confirm the predictions of this lower bound in a limited setting by showing a lower bound on the canonical degree-4 sum-of-squares relaxation for refuting random quadratic polynomials. Together, our results provide evidence for an algorithmic threshold for the problem at -time algorithms for all δ. Our upper-bound relies on establishing a sharp bound on the smallest integer d such that degree d–D polynomial combinations of the input pis generate all degree-d polynomials in the ideal generated by the pis. Our lower bound actually holds for the easier problem of distinguishing random polynomial systems as above from a distribution on polynomial systems with a “planted” solution. Our choice of planted distribution is slightly (and necessarily) subtle: it turns out that the natural and well-studied planted distribution for quadratic systems (studied as the matrix sensing problem in machine learning) is easily distinguishable whenever m ≥ Õ(n)–a factor n smaller than the threshold in our upper bound above. Thus, our setting provides an example where refutation is harder than search in the natural planted model.

We give a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in ℝd, for any fixed k, in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient partial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.

We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP with only the negation patterns of the literals re-randomized with some small probability. For an n-variable smoothed instance of a k-arity CSP, our algorithm runs in n^O(ℓ) time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from 1, provided that the number of constraints is at least Õ(n) (n/ell)^(k/2 - 1). This matches, up to polylogarithmic factors in n, the trade-off between running time and the number of constraints of the state-of-the-art algorithms for refuting fully random instances of CSPs.

We give the first polynomial time algorithm for list-decodable covariance estimation. For any α > 0, our algorithm takes input a sample Y ⊆ d of size n≥ dpoly(1/α) obtained by adversarially corrupting an (1−α)n points in an i.i.d. sample X of size n from the Gaussian distribution with unknown mean µ* and covariance Σ*. In npoly(1/α) time, it outputs a constant-size list of k = k(α)= (1/α)poly(1/α) candidate parameters that, with high probability, contains a (µ,Σ) such that the total variation distance TV(N(µ*,Σ*),N(µ,Σ))<1−Oα(1). This is a statistically strongest notion of distance and implies multiplicative spectral and relative Frobenius distance approximation with dimension independent error. Our algorithm works more generally for any distribution D that possesses low-degree sum-of-squares certificates of two natural analytic properties: 1) anti-concentration of one-dimensional marginals and 2) hypercontractivity of degree 2 polynomials.

We show that for constraint satisfaction problems (CSPs), weakly exponential size linear programming relaxations are as powerful as the explicit linear program described by $n^{\Omega(1)}$-rounds of the Sherali--Adams linear programming hierarchy. Combining with the known lower bounds on the Sherali--Adams hierarchy, we obtain subexponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly exponential improvement over previous results; previously, it was only known that linear programs of size $n^{o(\log n)}$ cannot beat random guessing for such CSP Chan et al. [FOCS 2013, IEEE, Piscataway, NJ, 2013, pp. 350--359]. Our bounds are obtained by exploiting and extending the recent progress in communication complexity for “lifting" query lower bounds to communication problems. The main ingredient in our results is a new structural result on “high-entropy rectangles” that may be of independent interest in communication complexity.

In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn x = (x₁,…,x_n) ∈ {0,1}ⁿ from a stream of random linear equations over 𝔽₂ that are correct with probability 1/2+ε and flipped with probability 1/2-ε (0 < ε < 1/2), that any learning algorithm requires either a memory of size Ω(n²/ε) or an exponential number of samples. In fact, we study memory-sample lower bounds for a large class of learning problems, as characterized by [Garg et al., 2018], when the samples are noisy. A matrix M: A × X → {-1,1} corresponds to the following learning problem with error parameter ε: an unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a₁, b₁), (a₂, b₂) …, where for every i, a_i ∈ A is chosen uniformly at random and b_i = M(a_i,x) with probability 1/2+ε and b_i = -M(a_i,x) with probability 1/2-ε (0 < ε < 1/2). Assume that k,𝓁, r are such that any submatrix of M of at least 2^{-k} ⋅ |A| rows and at least 2^{-𝓁} ⋅ |X| columns, has a bias of at most 2^{-r}. We show that any learning algorithm for the learning problem corresponding to M, with error parameter ε, requires either a memory of size at least Ω((k⋅𝓁)/ε), or at least 2^{Ω(r)} samples. The result holds even if the learner has an exponentially small success probability (of 2^{-Ω(r)}). In particular, this shows that for a large class of learning problems, same as those in [Garg et al., 2018], any learning algorithm requires either a memory of size at least Ω(((log|X|)⋅(log|A|))/ε) or an exponential number of noisy samples. Our proof is based on adapting the arguments in [Ran Raz, 2017; Garg et al., 2018] to the noisy case.

We prove that with high probability over the choice of a random graph G from the Erdős-Rényi distribution G(n, 1/2), a natural n^{O(ε² log n)}-time, degree O(ε² log n) sum-of-squares semidefinite program cannot refute the existence of a valid k-coloring of G for k = n^{1/2 + ε}. Our result implies that the refutation guarantee of the basic semidefinite program (a close variant of the Lovász theta function) cannot be appreciably improved by a natural o(log n)-degree sum-of-squares strengthening, and this is tight up to a n^{o(1)} slack in k. To the best of our knowledge, this is the first lower bound for coloring G(n, 1/2) for even a single round strengthening of the basic SDP in any SDP hierarchy. Our proof relies on a new variant of instance-preserving non-pointwise complete reduction within SoS from coloring a graph to finding large independent sets in it. Our proof is (perhaps surprisingly) short, simple and does not require complicated spectral norm bounds on random matrices with dependent entries that have been otherwise necessary in the proofs of many similar results [Boaz Barak et al., 2016; S. B. {Hopkins} et al., 2017; Dmitriy Kunisky and Afonso S. Bandeira, 2019; Mrinalkanti Ghosh et al., 2020; Mohanty et al., 2020]. Our result formally holds for a constraint system where vertices are allowed to belong to multiple color classes; we leave the extension to the formally stronger formulation of coloring, where vertices must belong to unique colors classes, as an outstanding open problem.

We give an efficient algorithm to strongly refute semi-random instances of all Boolean constraint satisfaction problems. The number of constraints required by our algorithm matches (up to polylogarithmic factors) the best known bounds for efficient refutation of fully random instances. Our main technical contribution is an algorithm to strongly refute semi-random instances of the Boolean k-XOR problem on n variables that have Õ(nk/2) constraints. (In a semi-random k-XOR instance, the equations can be arbitrary and only the right hand sides are random.) One of our key insights is to identify a simple combinatorial property of random XOR instances that makes spectral refutation work. Our approach involves taking an instance that does not satisfy this property (i.e., is not pseudorandom) and reducing it to a partitioned collection of 2-XOR instances. We analyze these subinstances using a carefully chosen quadratic form as proxy, which in turn is bounded via a combination of spectral methods and semidefinite programming. The analysis of our spectral bounds relies only on an off-the-shelf matrix Bernstein inequality. Even for the purely random case, this leads to a shorter proof compared to the ones in the literature that rely on problem-specific trace-moment computations.

In list-decodable subspace recovery, the input is a collection of n points αn (for some α ≪ 1/2) of which are drawn i.i.d. from a distribution D with a isotropic rank r covariance Π∗ (the inliers) and the rest are arbitrary, potential adversarial outliers. The goal is to recover a O(1/α) size list of candidate covariances that contains a close to Π∗. Two recent independent works [56, 3] gave algorithms for this problem that work whenever D satisfies an algorithmic variant of anti-concentration condition (certifiable anticoncentration). The running time of both these algorithms, however, is and the error bounds on ‖Π – Π∗‖F grow with r (polynomially in r in [56] and logarithmically in [3]) that can be as large as Ω(d). In this work, we improve on these results on all three fronts: we obtain dimension-independent error in fixed-polynomial running time under less restrictive distributional assumptions. Specifically, we give a poly(1/α)dO(1) time algorithm that outputs a list containing a satisfying . Our result only needs certifiable hypercontractivity of degree 2 polynomials -a condition satisfied by a much broader family of distributions in contrast to certifiable anticoncentration. As a result, in addition to Gaussians, our algorithm applies to uniform distribution on the hypercube and q-ary cubes and arbitrary product distributions with subgaussian marginals. Prior work [56] had identified such distributions as potential hard examples as such distributions do not exhibit strong enough anti-concentration. When D satisfies certifiable anti-concentration, we obtain a stronger error guarantee of for any arbitrary η > 0 in dO(poly(1/α)+log(1/η)) time. The proof of the first result uses certifiable hypercontractivity of degree 2 polynomials to give a low-degree sum-of-squares proof of identifiability of the low dimensional structure in the presence of overwhelming fraction of outliers in input data. Our second result relies on a novel bootstrapping of the guarantees from the first with a new exponential error reduction mechanism within SoS along with certifiable anti-concentration. 1

We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally speaking) “characterized” by a low-degree sum-of-squares proof. Our results are obtained by rounding low-entropy solutions — measured via a new global potential function — to sum-of-squares (SoS) semidefinite programs. This technique adds to the (currently short) list of general tools for analyzing SoS relaxations for worst-case optimization problems.

We study the expressive power of kernel methods and the algorithmic feasibility of multiple kernel learning for a special rich class of kernels. Specifically, we define Euclidean kernels, a diverse class that includes most, if not all, families of kernels studied in literature such as polynomial kernels and radial basis functions. We then describe the geometric and spectral structure of this family of kernels over the hypercube (and to some extent for any compact domain). Our structural results allow us to prove meaningful limitations on the expressive power of the class as well as derive several efficient algorithms for learning kernels over different domains.

In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. In our first result, we show that any algorithm that distinguishes between uniform distribution on $\{0,1\}^n$ and uniform distribution on an $n/2$-dimensional linear subspace of $\{0,1\}^n$ with non-negligible advantage needs $2^{Ω(n)}$ samples or $Ω(n^2)$ memory. Our second result applies to distinguishing outputs of Goldreich's local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreich's pseudorandom generator $G$ fixes a predicate $P:\{0,1\}^k \rightarrow \{0,1\}$ and a collection of subsets $S_1, S_2, \ldots, S_m \subseteq [n]$ of size $k$. For any seed $x \in \{0,1\}^n$, it outputs $P(x_{S_1}), P(x_{S_2}), \ldots, P(x_{S_m})$ where $x_{S_i}$ is the projection of $x$ to the coordinates in $S_i$. We prove that whenever $P$ is $t$-resilient (all non-zero Fourier coefficients of $(-1)^P$ are of degree $t$ or higher), then no algorithm, with $

We give the first outlier-robust efficient algorithm for clustering a mixture of k statistically separated d - dimensional Gaussians ( k-GMMs). Concretely, our algorithm takes input an ε-corrupted sample from a k-GMM and outputs an approximate clustering that misclassifies at most kO(k)(ε+η) fraction of the points whenever every pair of mixture components are separated by 1-exp(-poly(k/η)) in total variation distance. This is the statistically weakest possible notion of separation and allows, for e.g., clustering of mixtures with components with the same mean with covariances differing in a single unknown direction or separated in Frobenius distance. The running time of our algorithm is dpoly(k/η). Such results were not known prior to our work, even for k=2. More generally, our algorithms succeed for mixtures of any distribution that satisfies two well-studied analytic assumptions - sum-of-squares certifiable hypercontractivity and anti-concentration. As an immediate corollary, they extend to clustering mixtures of arbitrary affine transforms of the uniform distribution on the d-dimensional unit sphere. Even the information theoretic clusterability of separated distributions satisfying our analytic assumptions was not known and is likely to be of independent interest. Our algorithms build on the recent flurry of work relying on certifiable anti-concentration first introduced in [1], [2]. Our techniques expand the sum-of-squares toolkit to show robust certifiability of TV-separated Gaussian clusters in data. This involves giving a low-degree sum-of-squares proof of statements that relate parameter (i.e. mean and covariances) distance to total variation distance by relying only on hypercontractivity and anti-concentration.

We study efficient algorithms for Sparse PCA in standard statistical models (spiked covariance in its Wishart form). Our goal is to achieve optimal recovery guarantees while being resilient to small perturbations. Despite a long history of prior works, including explicit studies of perturbation resilience, the best known algorithmic guarantees for Sparse PCA are fragile and break down under small adversarial perturbations. We observe a basic connection between perturbation resilience and certifying algorithms that are based on certificates of upper bounds on sparse eigenvalues of random matrices. In contrast to other techniques, such certifying algorithms, including the brute-force maximum likelihood estimator, are automatically robust against small adversarial perturbation. We use this connection to obtain the first polynomial-time algorithms for this problem that are resilient against additive adversarial perturbations by obtaining new efficient certificates for upper bounds on sparse eigenvalues of random matrices. Our algorithms are based either on basic semidefinite programming or on its low-degree sum-of-squares strengthening depending on the parameter regimes. Their guarantees either match or approach the best known guarantees of fragile algorithms in terms of sparsity of the unknown vector, number of samples and the ambient dimension. To complement our algorithmic results, we prove rigorous lower bounds matching the gap between fragile and robust polynomial-time algorithms in a natural computational model based on low-degree polynomials (closely related to the pseudo-calibration technique for sum-of-squares lower bounds) that is known to capture the best known guarantees for related statistical estimation problems. The combination of these results provides formal evidence of an inherent price to pay to achieve robustness. Beyond these issues of perturbation resilience, our analysis also leads to new algorithms for the fragile setting, whose guarantees improve over best previous results in some parameter regimes (e.g. if the sample size is polynomially smaller than the dimension).

We consider a revenue-maximizing seller with n items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distinct options the buyer may purchase, up to permutations of the items. Our main result is that a mechanism of quasi-polynomial symmetric menu complexity suffices to guarantee a (1 - epsilon )-approximation when the buyer is unit-demand over independent items, even when the value distribution is unbounded, and that this mechanism can be found in quasi-polynomial time. Our key technical result is a polynomial-time, (symmetric) menu-complexity-preserving black-box reduction from achieving a (1 - epsilon )-approximation for unbounded valuations that are subadditive over independent items to achieving a (1 - O(epsilon ))-approximation when the values are bounded (and still subadditive over independent items). We further apply this reduction to deduce approximation schemes for a suite of valuation classes beyond our main result. Finally, we show that selling separately (which has exponential menu complexity) can be approximated up to a (1 - epsilon ) factor with a menu of efficient-linear (f (epsilon) · n) symmetric menu complexity.

Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain "Grassmanian agreement tester". In this work, we show that soundness of Grassmannian agreement tester follows from a conjecture we call the "Shortcode Expansion Hypothesis" characterizing the non-expanding sets of the degree-two Short code graph. We also show the latter conjecture is equivalent to a characterization of the non-expanding sets in the Grassman graph, as hypothesized by a follow-up paper of Dinur et al. (2017). Following our work, Khot, Minzer and Safra (2018) proved the "Shortcode Expansion Hypothesis". Combining their proof with our result and the reduction of Dinur et al. (2016), completes the proof of the 2 to 2 conjecture with imperfect completeness. We believe that the Shortcode graph provides a useful view of both the hypothesis and the reduction, and might be suitable for obtaining new hardness reductions.

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.

We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than 1/2 fraction of examples. For any \alpha < 1, our algorithm takes as input a sample {(xi,yi)}{i \leq n} of n linear equations where \alpha n of the equations satisfy yi = \langle x_i,\ell^\rangle +\zeta for some small noise \zeta and (1-\alpha) n of the equations are {\em arbitrarily} chosen. It outputs a list L of size O(1/\alpha) - a fixed constant - that contains an \ell that is close to \ell^. Our algorithm succeeds whenever the inliers are chosen from a certifiably anti-concentrated distribution D. In particular, this gives a (d/\alpha)^{O(1/\alpha^8)} time algorithm to find a O(1/\alpha) size list when the inlier distribution is a standard Gaussian. For discrete product distributions that are anti-concentrated only in regular directions, we give an algorithm that achieves similar guarantee under the promise that \ell^* has all coordinates of the same magnitude. To complement our result, we prove that the anti-concentration assumption on the inliers is information-theoretically necessary. To solve the problem we introduce a new framework for list-decodable learning that strengthens the ``identifiability to algorithms'' paradigm based on the sum-of-squares method.

A first line of attack in exploratory data analysis is \emph{data visualization}, i.e., generating a 2-dimensional representation of data that makes \emph{clusters} of similar points visually identifiable. Standard Johnson-Lindenstrauss dimensionality reduction does not produce data visualizations. The \emph{t-SNE} heuristic of van der Maaten and Hinton, which is based on non-convex optimization, has become the \emph{de facto} standard for visualization in a wide range of applications. This work gives a formal framework for the problem of data visualization – finding a 2-dimensional embedding of clusterable data that correctly separates individual clusters to make them visually identifiable. We then give a rigorous analysis of the performance of t-SNE under a natural, deterministic condition on the “ground-truth” clusters (similar to conditions assumed in earlier analyses of clustering) in the underlying data. These are the first provable guarantees on t-SNE for constructing good data visualizations. We show that our deterministic condition is satisfied by considerably general probabilistic generative models for clusterable data such as mixtures of well-separated log-concave distributions. Finally, we give theoretical evidence that t-SNE provably succeeds in \emph{partially} recovering cluster structure even when the above deterministic condition is not met.

We give the first polynomial-time algorithm for performing linear or polynomial regression resilient to adversarial corruptions in both examples and labels. Given a sufficiently large (polynomial-size) training set drawn i.i.d. from distribution ${\mathcal{D}}$ and subsequently corrupted on some fraction of points, our algorithm outputs a linear function whose squared error is close to the squared error of the best-fitting linear function with respect to ${\mathcal{D}}$, assuming that the marginal distribution of $\mathcal{D}$ over the input space is \emph{certifiably hypercontractive}. This natural property is satisfied by many well-studied distributions such as Gaussian, strongly log-concave distributions and, uniform distribution on the hypercube among others. We also give a simple statistical lower bound showing that some distributional assumption is necessary to succeed in this setting. These results are the first of their kind and were not known to be even information-theoretically possible prior to our work. Our approach is based on the sum-of-squares (SoS) method and is inspired by the recent applications of the method for parameter recovery problems in unsupervised learning. Our algorithm can be seen as a natural convex relaxation of the following conceptually simple non-convex optimization problem: find a linear function and a large subset of the input corrupted sample such that the least squares loss of the function over the subset is minimized over all possible large subsets.

The sample complexity of learning a Boolean-valued function class is precisely characterized by its Rademacher complexity. This has little bearing, however, on the sample complexity of efficient agnostic learning. We introduce refutation complexity, a natural computational analog of Rademacher complexity of a Boolean concept class and show that it exactly characterizes the sample complexity of efficient agnostic learning. Informally, refutation complexity of a class C is the minimum number of example-label pairs required to efficiently distinguish between the case that the labels correlate with the evaluation of some member of C (structure) and the case where the labels are i.i.d. Rademacher random variables (noise). The easy direction of this relationship was implicitly used in the recent framework for improper PAC learning lower bounds of Daniely and co-authors via connections to the hardness of refuting random constraint satisfaction problems. Our work can be seen as making the relationship between agnostic learning and refutation implicit in their work into an explicit equivalence. In a recent, independent work, Salil Vadhan discovered a similar relationship between refutation and PAC-learning in the realizable (i.e. noiseless) case.

Computing Nash equilibrium (NE) in two-player game is a central question in algorithmic game theory. The main motivation of this work is to understand the power of sum-of-squares method in computing equilibria, both exact and approximate. Previous works in this context have focused on hardness of approximating “best” equilibria with respect to some natural quality measure on equilibria such as social welfare. Such results, however, do not directly relate to the complexity of the problem of finding any equilibrium.

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers and design a new family of convex relaxations for k-means clustering based on sum-of-squares method. As an immediate corollary, for any γ > 0, we obtain an efficient algorithm for learning the means of a mixture of k arbitrary distributions in d in time dO(1/γ) so long as the means have separation Ω(kγ). This in particular yields an algorithm for learning Gaussian mixtures with separation Ω(kγ), thus partially resolving an open problem of Regev and Vijayaraghavan regev2017learning. The guarantees of our robust estimation algorithms improve in many cases significantly over the best previous ones, obtained in the recent works. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These improved guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers.

The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω > log ( n ) added to an Erdős-Rényi graph G ∼ G ( n ,1/2), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size ω = Ω (√ n ). By contrast, information theoretically, one can recover planted cliques so long as ω > log ( n ). In this work, we continue the investigation of algorithms from the Sum of Squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [2] and Deshpande and Montanari [25]. Our main result is that degree four SoS does not recover the planted clique unless ω > √ n / polylog n , improving on the bound ω > n 1/3 due to Reference [25]. An argument of Kelner shows that the this result cannot be proved using the same certificate as prior works. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by “correcting” the certificate of References [2, 25, 27].

We study planted problems-finding hidden structures in random noisy inputs-through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of powerful semidefinite programs has recently yielded many new algorithms for planted problems, often achieving the best known polynomial-time guarantees in terms of accuracy of recovered solutions and robustness to noise. One theme in recent work is the design of spectral algorithms which match the guarantees of SoS algorithms for planted problems. Classical spectral algorithms are often unable to accomplish this: the twist in these new spectral algorithms is the use of spectral structure of matrices whose entries are low-degree polynomials of the input variables. We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-ksubgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials are as powerful as SoS semidefinite programs of degree d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program. Using related ideas on SoS algorithms and lowdegree matrix polynomials (and inspired by recent work on SoS and the planted clique problem [BHK+16]), we prove a new SoS lower bound for the tensor PCA problem.

For every constant ε>0, we give an exp(Õ(∞n))-time algorithm for the 1 vs 1 - ε Best Separable State (BSS) problem of distinguishing, given an n2 x n2 matrix ℳ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state ρ that ℳ accepts with probability 1, and the case that every separable state is accepted with probability at most 1 - ε. Equivalently, our algorithm takes the description of a subspace 𝒲 ⊆ 𝔽n2 (where 𝔽 can be either the real or complex field) and distinguishes between the case that contains a rank one matrix, and the case that every rank one matrix is at least ε far (in 𝓁2 distance) from 𝒲.

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 show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as nΩ(1)-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly-exponential improvement over previous results; previously, the best known lower bounds were quasi-polynomial in n (Chan, Lee, Raghavendra, Steurer 2013).

We prove that with high probability over the choice of a random graph G from the Erdös-Rényi distribution G(n,1/2), the nO(d)-time degree d Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least n1/2-c(d/log n)1/2for some constant c > 0. This yields a nearly tight n1/2-o(1)bound on the value of this program for any degree d = o(log n). Moreover we introduce a new framework that we call pseudo-calibration to construct Sum-of-Squares lower bounds. This framework is inspired by taking a computational analogue of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information x and Bob gets y, where (x, y) is drawn from a known distribution, and Bob wishes to compute some function g(x, y) (with high probability over (x, y)). In our variant, Alice does not know g, but only knows some function f which is an approximation of g. Thus, the function being computed forms the context for the communication, and knowing it imperfectly models (mild) uncertainty in this context. A naive solution would be for Alice and Bob to first agree on some common function h that is close to both f and g and then use a protocol for h to compute h(x, y). We show that any such agreement leads to a large overhead in communication ruling out such a universal solution. In contrast, we show that if g has a one-way communication protocol with complexity k in the standard setting, then it has a communication protocol with complexity O(k · (1 + I)) in the uncertain setting, where I denotes the mutual information between x and y. In the particular case where the input distribution is a product distribution, the protocol in the uncertain setting only incurs a constant factor blow-up in communication and error. Furthermore, we show that the dependence on the mutual information I is required. Namely, we construct a class of functions along with a non-product distribution over (x, y) for which the communication complexity is a single bit in the standard setting but at least bits in the uncertain setting.

The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω ≫ log (n) added to an Erdős-Rényi graph , have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size . By contrast, information theoretically, one can recover planted cliques so long as ω ≫ log (n). In this work, we continue the investigation of algorithms from the sum of squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [MPW15] and Deshpande and Montanari [DM15b]. Our main results improve upon both these previous works by showing: 1. Degree four SoS does not recover the planted clique unless , improving upon the bound ω ≫ n1/3 due to [DM15b]. 2. For , degree 2d SoS does not recover the planted clique unless ω ≫ n1/(d+1)/(2d polylog n), improving upon the bound due to [MPW15]. Our proof for the second result is based on a fine spectral analysis of the certificate used in the prior works [MPW15, DM15b, FK03] by decomposing it along an appropriately chosen basis. Along the way, we develop combinatorial tools to analyze the spectrum of random matrices with dependent entries and to understand the symmetries in the eigenspaces of the set symmetric matrices inspired by work of Grigoriev [Gri01a] An argument of Kelner shows that the first result cannot be proved using the same certificate. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by “correcting” the certificate of [MPW15, DM15b, FK03]

We prove that for every ε>0 and predicate P:{0,1}k-> {0,1} that supports a pairwise independent distribution, there exists an instance I of the Max P constraint satisfaction problem on n variables such that no assignment can satisfy more than a ~(|P-1(1)|)/(2k)+ε fraction of I's constraints but the degree Ω(n) Sum of Squares semidefinite programming hierarchy cannot certify that I is unsatisfiable. Similar results were previously only known for weaker hierarchies.

Halfspaces or linear threshold functions are widely studied in complexity theory, learning theory and algorithm design. In this work we study the natural problem of constructing pseudorandom generators (PRGs) for halfspaces over the sphere, aka spherical caps, which besides being interesting and basic geometric objects, also arise frequently in the analysis of various randomized algorithms (e.g., randomized rounding). We give an explicit PRG which fools spherical caps within error ε and has an almost optimal seed-length of O(log n + log(1/ε) ⋅ log log(1/ε)). For an inverse-polynomially growing error ε, our generator has a seed-length optimal up to a factor of O( log log (n)). The most efficient PRG previously known (due to Kane 2012) requires a seed-length of Ω(log3/2(n)) in this setting. We also obtain similar constructions to fool halfspaces with respect to the Gaussian distribution. Our construction and analysis are significantly different from previous works on PRGs for halfspaces and build on the iterative dimension reduction ideas of Kane et. al. 2011 and Celis et. al. 2013, the classical moment problem from probability theory and explicit constructions of approximate orthogonal designs based on the seminal work of Bourgain and Gamburd 2011 on expansion in Lie groups.

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in theoretical computer science and show that any algorithm for agnostically learning halfspaces requires n^Omega(log(1/\epsilon)) time under the assumption that k-sparse LPN requires n^Omega(k) time, ruling out a polynomial time algorithm for the problem. As far as we are aware, this is the first representation-independent hardness result for supervised learning when the underlying distribution is restricted to be a Gaussian. We also show that the problem of agnostically learning sparse polynomials with respect to the Gaussian distribution in polynomial time is as hard as PAC learning DNFs on the uniform distribution in polynomial time. This complements the surprising result of Andoni et. al. 2013 who show that sparse polynomials are learnable under random Gaussian noise in polynomial time. Taken together, these results show the inherent difficulty of designing supervised learning algorithms in Euclidean space even in the presence of strong distributional assumptions. Our results use a novel embedding of random labeled examples from the uniform distribution on the Boolean hypercube into random labeled examples from the Gaussian distribution that allows us to relate the hardness of learning problems on two different domains and distributions.

We study the problem of approximating and learning coverage functions. A function c: 2^[n] →\mathbfR^+ is a coverage function, if there exists a universe U with non-negative weights w(u) for each u ∈U and subsets A_1, A_2, \ldots, A_n of U such that c(S) = \sum_u ∈\cup_i ∈S A_i w(u). Alternatively, coverage functions can be described as non-negative linear combinations of monotone disjunctions. They are a natural subclass of submodular functions and arise in a number of applications. We give an algorithm that for any γ,δ>0, given random and uniform examples of an unknown coverage function c, finds a function h that approximates c within factor 1+γon all but δ-fraction of the points in time poly(n,1/γ,1/δ). This is the first fully-polynomial algorithm for learning an interesting class of functions in the demanding PMAC model of Balcan and Harvey (2011). Our algorithms are based on several new structural properties of coverage functions. Using the results in (Feldman and Kothari, 2014), we also show that coverage functions are learnable agnostically with excess \ell_1-error εover all product and symmetric distributions in time n^\log(1/ε). In contrast, we show that, without assumptions on the distribution, learning coverage functions is at least as hard as learning polynomial-size disjoint DNF formulas, a class of functions for which the best known algorithm runs in time 2^\tildeO(n^1/3) (Klivans and Servedio, 2004). As an application of our learning results, we give simple differentially-private algorithms for releasing monotone conjunction counting queries with low \em average error. In particular, for any k ≤n, we obtain private release of k-way marginals with average error \barα in time n^O(\log(1/\barα)).

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.

Fort now and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class of boolean circuits C contained in P/poly of Boolean is exactly learnable with membership and equivalence queries in polynomial-time, then EXP^NP is not contained in C (the class EXP^NP was subsequently improved to EXP by Hitchcock and Harkins). In this paper, we improve on these results and show * If C is exactly learnable with membership and equivalence queries in polynomial-time, then DTIME(n^{\omega(1)}) is not contained in C. We obtain even stronger consequences if C is learnable in the mistake-bounded model, in which case we prove an average-case hardness result against C. * If C is learnable in polynomial time in the PAC model then PSPACE is not contained in C, unless PSPACE is contained in BPP. Removing this extra assumption from the statement of the theorem would provide an unconditional separation of PSPACE and BPP. * If C is efficiently learnable in the Correlational Statistical Query (CSQ) model, we show that there exists an explicit function f that is average-case hard for circuits in C. This result provides stronger average-case hardness guarantees than those obtained by SQ-dimension arguments (Blum et al. 1993). We also obtain a non-constructive extension of this result to the stronger Statistical Query (SQ) model. Similar results hold in the case where the learning algorithm runs in sub exponential time. Our proofs regarding exact and mistake-bounded learning are simple and self-contained, yield explicit hard functions, and show how to use mistake-bounded learners to "diagonalize"' over families of polynomial-size circuits. Our consequences for PAC learning lead to new proofs of Karp-Lipton-style collapse results, and the lower bounds from SQ learning make use of recent work relating combinatorial discrepancy to the existence of hard-on-average functions.

We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube {0,1}^n. Our main result is the following structural theorem: any submodular function is ε-close in \ell_2 to a real-valued decision tree (DT) of depth O(1/ε^2). This immediately implies that any submodular function is ε-close to a function of at most 2^O(1/ε^2) variables and has a spectral \ell_1 norm of 2^O(1/ε^2). It also implies the closest previous result that states that submodular functions can be approximated by polynomials of degree O(1/ε^2) (Cheraghchi et al., 2012). Our result is proved by constructing an approximation of a submodular function by a DT of rank 4/ε^2 and a proof that any rank-r DT can be ε-approximated by a DT of depth \frac52(r+\log(1/ε)). We show that these structural results can be exploited to give an attribute-efficient PAC learning algorithm for submodular functions running in time \tildeO(n^2) ⋅2^O(1/ε^4). The best previous algorithm for the problem requires n^O(1/ε^2) time and examples (Cheraghchi et al., 2012) but works also in the agnostic setting. In addition, we give improved learning algorithms for a number of related settings. We also prove that our PAC and agnostic learning algorithms are essentially optimal via two lower bounds: (1) an information-theoretic lower bound of 2^Ω(1/ε^2/3) on the complexity of learning monotone submodular functions in any reasonable model (including learning with value queries); (2) computational lower bound of n^Ω(1/ε^2/3) based on a reduction to learning of sparse parities with noise, widely-believed to be intractable. These are the first lower bounds for learning of submodular functions over the uniform distribution.

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on {−1, 1}n (for any constant accuracy parameter ∊). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular functions required either query access or strong assumptions about the types of submodular functions to be learned (and did not hold in the agnostic setting). Additionally we give simple algorithms that efficiently release differentially private answers to all Boolean conjunctions and to all halfspaces with constant average error, subsuming and improving recent work due to Gupta, Hardt, Roth and Ullman (STOC 2011).

This paper presents a randomized scheduler for finding concurrency bugs. Like current stress-testing methods, it repeatedly runs a given test program with supplied inputs. However, it improves on stress-testing by finding buggy schedules more effectively and by quantifying the probability of missing concurrency bugs. Key to its design is the characterization of the depth of a concurrency bug as the minimum number of scheduling constraints required to find it. In a single run of a program with n threads and k steps, our scheduler detects a concurrency bug of depth d with probability at least 1/nkd-1. We hypothesize that in practice, many concurrency bugs (including well-known types such as ordering errors, atomicity violations, and deadlocks) have small bug-depths, and we confirm the efficiency of our schedule randomization by detecting previously unknown and known concurrency bugs in several production-scale concurrent programs.