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.

We study community detection in the \emph{symmetric $k$-stochastic block model}, where $n$ nodes are evenly partitioned into $k$ clusters with intra- and inter-cluster connection probabilities $p$ and $q$, respectively. Our main result is a polynomial-time algorithm that achieves the optimal misclassification rate $\exp(-(1 \pm o(1)) C/k)$, where $C = (\sqrt{pn} - \sqrt{qn})^2$, whenever $C \geq K k^2 \log k$ for some universal constant $K$, matching the Kesten–Stigum ({KS}) threshold up to a $\log k$ factor. Notably, this rate holds even when an adversary corrupts an $\eta \leq \exp(-(1 \pm o(1)) C/k)$ fraction of the nodes. To the best of our knowledge, this optimal error rate was previously only attainable either via computationally inefficient procedures (Zhang and Zhou, 2015) or via polynomial-time algorithms that require strictly stronger assumptions such as $C \geq K k^3$ (Gao et al., 2017). In the node-robust setting, the best known algorithm requires the substantially stronger condition $C \geq K k^{102}$ (Liu and Moitra, 2022). Our results close this gap by providing the first polynomial-time algorithm that achieves the optimal error rate near the {KS} threshold in both settings. Our work has two key technical contributions: (1) we robustify majority voting via the Sum-of-Squares framework, (2) we develop a novel graph bisectioning algorithm via robust majority voting, which allows us to significantly improve the misclassification rate to $1/\mathrm{poly}(k)$ for the initial estimation near the {KS} threshold.

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS’24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy $\varepsilon > 0$ and dimension $d$ we give an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to error $\varepsilon$ in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of $d$ and $\varepsilon$ even \emph{without} truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

Efficient algorithms for convex optimization, such as the ellipsoid method, require an a priori bound on the radius of a ball around the origin guaranteed to contain an optimal solution if one exists. For linear and convex quadratic programming, such solution bounds follow from classical characterizations of optimal solutions by systems of linear equations. For other programs, e.g., semidefinite ones, examples due to Khachiyan show that optimal solutions may require huge coefficients with an exponential number of bits, even if we allow approximations. Correspondingly, semidefinite programming is not even known to be in NP.

We establish new algorithmic guarantees with matching hardness results for coloring and independent set problems in one-sided expanders and related classes of graphs. For example, given a 3-colorable regular one-sided expander, we compute in polynomial time either an independent set of relative size at least $\frac{1}{2}-o(1)$ or a proper 3-coloring for all but an $o(1)$ fraction of the vertices, where $o(1)$ stands for a function that tends to 0 with the second largest eigenvalue of the normalized adjacency matrix. This result improves on recent seminal work of Bafna, Hsieh, and Kothari (STOC 2025) developing an algorithm that efficiently finds independent sets of relative size at least 0.01 in such graphs. We also obtain an efficient 1.6667-factor approximation algorithm for VERTEX COVER in sufficiently strong regular one-sided expanders, improving over a previous $(2-\varepsilon)$-factor approximation in such graphs for an unspecified constant $\varepsilon\gt 0$. We propose a new stratification of k-COLORING in terms of k-by- k matrices akin to predicate sets for constraint satisfaction problems. We prove that whenever this matrix has repeated rows, the corresponding coloring problem is NP-hard for one-sided expanders under the Unique Games Conjecture. On the other hand, if this matrix has no repeated rows, our algorithms can solve the corresponding coloring problem on one-sided expanders in polynomial time. When this k-by- k matrix has repeated rows, we furthermore characterize the maximum fraction of vertices on which a proper k-coloring can be found by polynomial-time algorithms under the Unique Games Conjecture. As starting point for our algorithmic results, we show a property of graph spectra that, to the best of our knowledge, has not been observed before: The number of negative eigenvalues smaller than $-\tau$ is at most $O\left(1 / \tau^{2}\right)$ times the number of eigenvalues larger than $\tau^{2} / 2$. While this result allows us to bound the number of eigenvalues bounded away from 0 in one-sided spectral expanders, this property alone is insufficient for our algorithmic results. For example, given a one-sided regular expander with a balanced 3 -coloring, we can efficiently find a 3 -coloring for all but a $o(1)$ fraction of vertices. At the same time, if we only know that the graph has a balanced 3 -coloring and a bounded number of significant eigenvalues, it is NP-hard under the Unique Games Conjecture to find a 3 -coloring for all but a 0.1 fraction of vertices.

We investigate implications of the (extended) low-degree conjecture (recently formalized in [moitra et al2023]) in the context of the symmetric stochastic block model. Assuming the conjecture holds, we establish that no polynomial-time algorithm can weakly recover community labels below the Kesten-Stigum (KS) threshold. In particular, we rule out polynomial-time estimators that, with constant probability, achieve $n^{-0.49}$ correlation with the true communities. Whereas, above the KS threshold, polynomial-time algorithms are known to achieve constant correlation with the true communities with high probability [massoulie et al 2014,abbe et al 2015]. To our knowledge, we provide the first rigorous evidence for such sharp transition in recovery rate for polynomial-time algorithms at the KS threshold. Notably, under a stronger version of the low-degree conjecture, our lower bound remains valid even when the number of blocks diverges. Furthermore, our results provide evidence of a computational-to-statistical gap in learning the parameters of stochastic block models. In contrast, prior work either (i) rules out polynomial-time algorithms with $1 - o(1)$ success probability [Hopkins 18, bandeira et al 2021] under the low-degree conjecture, or (ii) degree-$\text{poly}(k)$ polynomials for learning the stochastic block model [Luo et al 2023]. For this, we design a hypothesis test which succeeeds with constant probability under symmetric stochastic block model, and $1-o(1)$ probability under the distribution of \Erdos \Renyi random graphs. Our proof combines low-degree lower bounds from [Hopkins 18, bandeira et al 2021] with graph splitting and cross-validation techniques. In order to rule out general recovery algorithms, we employ the correlation preserving projection method developed in [Hopkins et al 17].

We revisit the problem of estimating the mean of a high-dimensional distribution in the presence of an ε-fraction of adversarial outliers. When ε is at most some sufficiently small constant, previous works can achieve optimal error rate efficiently [DKK+18, KSS18]. As ɛ approaches the breakdown point , all previous algorithms incur either sub-optimal error rates or exponential running time. In this paper we give a new analysis of the canonical sum-of-squares program introduced in [KSS18] and show that this program efficiently achieves optimal error rate for all ɛ ∈ [0, ). The key ingredient for our results is a new identifiability proof for robust mean estimation that focuses on the overlap between the distributions instead of their statistical distance as in previous works. We capture this proof within the sum-of-squares proof system, thus obtaining efficient algorithms using the sum-of-squares proofs to algorithms paradigm [RSS18].

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 the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of Erdős-Rényi random graphs and their generalization, inhomogeneous random graphs. We further prove information-theoretical lower bounds, showing that the error rate of our algorithm is optimal up to logarithmic factors. Previous algorithms incur either exponential running time or suboptimal error rates. Two key ingredients of our algorithm are (1) a new sum-of-squares algorithm for robust edge density estimation, and (2) the reduction from privacy to robustness based on sum-of-squares exponential mechanisms due to Hopkins et al. (STOC 2023).

We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fraction is significantly smaller than the minimum mixing weight, much less is known when outliers may crowd out low-weight clusters – a setting we refer to as list-decodable mixture learning (LD-ML). In this case, adversarial outliers can simulate additional spurious mixture components. Hence, if all means of the mixture must be recovered up to a small error in the output list, the list size needs to be larger than the number of (true) components. We propose an algorithm that obtains order-optimal error guarantees for each mixture mean with a minimal list-size overhead, significantly improving upon list-decodable mean estimation, the only existing method that is applicable for LD-ML. Although improvements are observed even when the mixture is non-separated, our algorithm achieves particularly strong guarantees when the mixture is separated: it can leverage the mixture structure to partially cluster the samples before carefully iterating a base learner for list-decodable mean estimation at different scales.

We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant number of blocks. The statistical utility guarantees match those of the previous best information-theoretic (exponential-time) node-private mechanisms for these problems. The algorithm is based on an exponential mech- anism for a score function defined in terms of a sum-of-squares relaxation whose level depends on the number of blocks. The key ingredients of our results are (1) a characterization of the distance between the block graphons in terms of a quadratic optimization over the polytope of doubly stochastic matrices, (2) a general sum-of-squares convergence result for polynomial op- timization over arbitrary polytopes, and (3) a general approach to perform Lipschitz extensions of score functions as part of the sum-of-squares algorithmic paradigm.

We consider mixtures of k >= 2 Gaussian components with unknown means and unknown covariance (identical for all components) that are well-separated, i.e., distinct components have statistical overlap at most k^{-C} for a large enough constant C >= 1.Previous statistical-query [DKS17] and cryptographic [BRST21, GVV22] lower bounds give formal evidence that, even for the special case of colinear means, distinguishing such mixtures from (pure) Gaussians may be exponentially hard (in k).We show that, surprisingly, this kind of hardness can only appear if mixing weights are allowed to be exponentially small. For polynomially lower bounded mixing weights, we show how to achieve non-trivial statistical guarantees in quasi-polynomial time.Concretely, we develop an algorithm based on the sum-of-squares method with running time quasi-polynomial in the minimum mixing weight. The algorithm can reliably distinguish between a mixture of k >= 2 well-separated Gaussian components and a (pure) Gaussian distribution. As a certificate, the algorithm computes a bipartition of the input sample that separates some pairs of mixture components, i.e., both sides of the bipartition contain most of the sample points of at least one component.For the special case of colinear means, our algorithm outputs a k-clustering of the input sample that is approximately consistent with all components of the underlying mixture. We obtain similar clustering guarantees also for the case that the overlap between any two mixture components is lower bounded quasi-polynomially ink (in addition to being upper bounded polynomially in k).A significant challenge for our results is that they appear to be inherently sensitive to small fractions of adversarial outliers unlike most previous algorithmic results for Gaussian mixtures. The reason is that such outliers can simulate exponentially small mixing weights even for mixtures with polynomially lower bounded mixing weights.A key technical ingredient of our algorithms is a characterization of separating directions for well-separated Gaussian components in terms of ratios of polynomials that correspond to moments of two carefully chosen orders logarithmic in the minimum mixing weight.

We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the n vertices. We present the first polynomial-time algorithm that achieves weak recovery at the Kesten-Stigum threshold even in the presence of a small constant fraction of corrupted nodes. Prior to this work, even state-of-the-art robust algorithms were known to break under such node corruption adversaries, when close to the Kesten-Stigum threshold.We further extend our techniques to the $Z_2$ synchronization problem, where our algorithm reaches the optimal recovery threshold in the presence of similar strong adversarial perturbations.The key ingredient of our algorithm is a novel identifiability proof that leverages the push-out effect of the Grothendieck norm of principal submatrices.

We introduce general tools for designing efficient private estimation algorithms, in the high-dimensional settings, whose statistical guarantees almost match those of the best known non-private algorithms. To illustrate our techniques, we consider two problems: recovery of stochastic block models and learning mixtures of spherical Gaussians. For the former, we present the first efficient $(\epsilon, \delta)$-differentially private algorithm for both weak recovery and exact recovery. Previously known algorithms achieving comparable guarantees required quasi-polynomial time. For the latter, we design an $(\epsilon, \delta)$-differentially private algorithm that recovers the centers of the $k$-mixture when the minimum separation is at least $ O(k^{1/t}\sqrt{t})$. For all choices of $t$, this algorithm requires sample complexity $n\geq k^{O(1)}d^{O(t)}$ and time complexity $(nd)^{O(t)}$. Prior work required either an additional additive $\Omega(\sqrt{\log n})$ term in the minimum separation or an explicit upper bound on the Euclidean norm of the centers.

We study the problem of robustly estimating the mean or location parameter without moment assumptions. Known computationally efficient algorithms rely on strong distributional assumptions, such as sub-Gaussianity, or (certifiably) bounded moments. Moreover, the guarantees that they achieve in the heavy-tailed setting are weaker than those for sub-Gaussian distributions with known covariance. In this work, we show that such a tradeoff, between error guarantees and heavy-tails, is not necessary for symmetric distributions. We show that for a large class of symmetric distributions, the same error as in the Gaussian setting can be achieved efficiently. The distributions we study include products of arbitrary symmetric one-dimensional distributions, such as product Cauchy distributions, as well as elliptical distributions, a vast generalization of the Gaussian distribution. For product distributions and elliptical distributions with known scatter (covariance) matrix, we show that given an $\varepsilon$-corrupted sample, we can with probability at least $1-\delta$ estimate its location up to error $O(\varepsilon \sqrt{\log(1/\varepsilon)})$ using $\tfrac{d\log(d) + \log(1/\delta)}{\varepsilon^2 \log(1/\varepsilon)}$ samples. This result matches the best-known guarantees for the Gaussian distribution and known SQ lower bounds (up to the $\log(d)$ factor). For elliptical distributions with unknown scatter (covariance) matrix, we propose a sequence of efficient algorithms that approaches this optimal error. Specifically, for every $k \in \mathbb{N}$, we design an estimator using time and samples $\tilde{O}({d^k})$ achieving error $O(\varepsilon^{1-\frac{1}{2k}})$. This matches the error and running time guarantees when assuming certifiably bounded moments of order up to $k$. For unknown covariance, such error bounds of $o(\sqrt{\varepsilon})$ are not even known for (general) sub-Gaussian distributions. Our algorithms are based on a generalization of the well-known filtering technique [DK22]. More specifically, we show how this machinery can be combined with Huber-loss-based techniques to work with projections of the noise that behave more nicely than the initial noise. Moreover, we show how sum-of-squares proofs can be used to obtain algorithmic guarantees even for distributions without a first moment. We believe that this approach may find other applications in future works.

We consider estimation models of the form Y = X* + N, where X* is some m-dimensional structured signal we wish to recover, and N is symmetrically distributed noise that may be unbounded in all but a small α fraction of the entries. This setting captures problems such as (sparse) linear regression, (sparse) principal component analysis (PCA), and tensor PCA, even in the presence of oblivious outliers and heavy-tailed noise. We introduce a family of algorithms that under mild assumptions recover the signal X* in all estimation problems for which there exists a sum-of-squares algorithm that succeeds in recovering the signal X* when the noise N is Gaussian. This essentially shows that it is enough to design a sum-of-squares algorithm for an estimation problem with Gaussian additive noise in order to get the algorithm that works with the symmetric noise model. Our framework extends far beyond previous results on symmetric noise models and is even robust to an ε-fraction of adversarial perturbations. As concrete examples, we investigate two problems for which no efficient algorithms were known to work for heavy-tailed noise: tensor PCA and sparse PCA. For the former, our algorithm recovers the principal component in polynomial time when the signal-to-noise ratio is at least Õ(np/4/ α), that matches (up to logarithmic factors) current best known algorithmic guarantees for Gaussian noise. For the latter, our algorithm runs in quasipolynomial time and matches the state-of-the-art guarantees for quasipolynomial time algorithms in the case of Gaussian noise. Using a reduction from the planted clique problem, we provide evidence that the quasipolynomial time is likely to be necessary for sparse PCA with symmetric noise. In our proofs we use bounds on the covering numbers of sets of pseudo-expectations, which we obtain by certifying in sum-of-squares upper bounds on the Gaussian complexities of sets of solutions. This approach for bounding the covering numbers of sets of pseudo-expectations may be interesting in its own right and may find other application in future works. * This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 815464).

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.

We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to $$O(d^{3/2}/polylog(d))$$. Our algorithm only involves simple linear algebra operations and can recover all components in time $$O(d^{6.05})$$ under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most $$O(d^{4/3}/polylog(d))$$. Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm.

We develop an efficient algorithm for weak recovery in a robust version of the stochastic block model. The algorithm matches the statistical guarantees of the best known algorithms for the vanilla version of the stochastic block model. In this sense, our results show that there is no price of robustness in the stochastic block model. Our work is heavily inspired by recent work of Banks, Mohanty, and Raghavendra (SODA 2021) that provided an efficient algorithm for the corresponding distinguishing problem. Our algorithm and its analysis significantly depart from previous ones for robust recovery. A key challenge is the peculiar optimization landscape underlying our algorithm: The planted partition may be far from optimal in the sense that completely unrelated solutions could achieve the same objective value. This phenomenon is related to the push-out effect at the BBP phase transition for PCA. To the best of our knowledge, our algorithm is the first to achieve robust recovery in the presense of such a push-out effect in a non-asymptotic setting. Our algorithm is an instantiation of a framework based on convex optimization (related to but distinct from sum-of-squares), which may be useful for other robust matrix estimation problems. A by-product of our analysis is a general technique that boosts the probability of success (over the randomness of the input) of an arbitrary robust weak-recovery algorithm from constant (or slowly vanishing) probability to exponentially high probability.

We consider a robust linear regression model $y=X\beta^* + \eta$, where an adversary oblivious to the design $X\in \mathbb{R}^{n\times d}$ may choose $\eta$ to corrupt all but an $\alpha$ fraction of the observations $y$ in an arbitrary way. Prior to our work, even for Gaussian $X$, no estimator for $\beta^*$ was known to be consistent in this model except for quadratic sample size $n \gtrsim (d/\alpha)^2$ or for logarithmic inlier fraction $\alpha\ge 1/\log n$. We show that consistent estimation is possible with nearly linear sample size and inverse-polynomial inlier fraction. Concretely, we show that the Huber loss estimator is consistent for every sample size $n= \omega(d/\alpha^2)$ and achieves an error rate of $O(d/\alpha^2n)^{1/2}$ (both bounds are optimal up to constant factors). Our results extend to designs far beyond the Gaussian case and only require the column span of $X$ to not contain approximately sparse vectors (similar to the kind of assumption commonly made about the kernel space for compressed sensing). We provide two technically similar proofs. One proof is phrased in terms of strong convexity, extending work of [Tsakonas et al. ’14], and particularly short. The other proof highlights a connection between the Huber loss estimator and high-dimensional median computations. In the special case of Gaussian designs, this connection leads us to a strikingly simple algorithm based on computing coordinate-wise medians that achieves nearly optimal guarantees in linear time, and that can exploit sparsity of $\beta^*$. The model studied here also captures heavy-tailed noise distributions that may not even have a first moment.

We develop machinery to design efficiently computable and \emph{consistent} estimators, achieving estimation error approaching zero as the number of observations grows, when facing an oblivious adversary that may corrupt responses in all but an $\alpha$ fraction of the samples.As concrete examples, we investigate two problems: sparse regression and principal component analysis (PCA).For sparse regression, we achieve consistency for optimal sample size $n\gtrsim (k\log d)/\alpha^2$ and optimal error rate $O(\sqrt{(k\log d)/(n\cdot \alpha^2)})$where $n$ is the number of observations, $d$ is the number of dimensions and $k$ is the sparsity of the parameter vector, allowing the fraction of inliers to be inverse-polynomial in the number of samples.Prior to this work, no estimator was known to be consistent when the fraction of inliers $\alpha$ is $o(1/\log \log n)$, even for (non-spherical) Gaussian design matrices.Results holding under weak design assumptions and in the presence of such general noise have only been shown in dense setting (i.e., general linear regression) very recently by d'Orsi et al.~\cite{ICML-linear-regression}.In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix (usually used in matrix completion). Previous works could obtain non-trivial guarantees only under the assumptions that the measurement noise corresponding to the inliers is polynomially small in $n$ (e.g., Gaussian with variance $1/n^2$).To devise our estimators, we equip the Huber loss with non-smooth regularizers such as the $\ell_1$ norm or the nuclear norm, and extend d'Orsi et al.'s approach~\cite{ICML-linear-regression} in a novel way to analyze the loss function.Our machinery appears to be easily applicable to a wide range of estimation problems.We complement these algorithmic results with statistical lower bounds showing that the fraction of inliers that our PCA estimator can deal with is optimal up to a constant factor.

We develop a general framework to significantly reduce the degree of sum-of-squares proofs by introducing new variables. To illustrate the power of this framework, we use it to speed up previous algorithms based on sum-of-squares for two important estimation problems, clustering and robust moment estimation. The resulting algorithms offer the same statistical guarantees as the previous best algorithms but have significantly faster running times. Roughly speaking, given a sample of n points in dimension d, our algorithms can exploit order-ℓ moments in time dO(ℓ) · nO(1), whereas a naive implementation requires time (d · n)O(ℓ). Since for the aforementioned applications, the typical sample size is dΘ(ℓ), our framework improves running times from to dO(ℓ).

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 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 study symmetric spiked matrix models with respect to a general class of noise distributions. Given a rank-1 deformation of a random noise matrix, whose entries are independently distributed with zero mean and unit variance, the goal is to estimate the rank-1 part. For the case of Gaussian noise, the top eigenvector of the given matrix is a widely-studied estimator known to achieve optimal statistical guarantees, e.g., in the sense of the celebrated BBP phase transition. However, this estimator can fail completely for heavy-tailed noise. In this work, we exhibit an estimator that works for heavy-tailed noise up to the BBP threshold that is optimal even for Gaussian noise. We give a non-asymptotic analysis of our estimator which relies only on the variance of each entry remaining constant as the size of the matrix grows: higher moments may grow arbitrarily fast or even fail to exist. Previously, it was only known how to achieve these guarantees if higher-order moments of the noises are bounded by a constant independent of the size of the matrix. Our estimator can be evaluated in polynomial time by counting self-avoiding walks via a color coding technique. Moreover, we extend our estimator to spiked tensor models and establish analogous results.

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.

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.

We obtain the first polynomial-time algorithm for exact tensor completion that improves over the bound implied by reduction to matrix completion. The algorithm recovers an unknown 3-tensor with $r$ incoherent, orthogonal components in $\mathbb R^n$ from $r⋅\tilde O(n^1.5)$ randomly observed entries of the tensor. This bound improves over the previous best one of $r⋅\tilde O(n^2)$ by reduction to exact matrix completion. Our bound also matches the best known results for the easier problem of approximate tensor completion (Barak & Moitra, 2015). Our algorithm and analysis extends seminal results for exact matrix completion (Candes & Recht, 2009) to the tensor setting via the sum-of-squares method. The main technical challenge is to show that a small number of randomly chosen monomials are enough to construct a degree-3 polynomial with precisely planted orthogonal global optima over the sphere and that this fact can be certified within the sum-of-squares proof system.

We develop fast spectral algorithms for tensor decomposition that match the robustness guarantees of the best known polynomial-time algorithms for this problem based on the sum-of-squares (SOS) semidefinite programming hierarchy. Our algorithms can decompose a 4-tensor with $n$-dimensional orthonormal components in the presence of error with constant spectral norm (when viewed as an $n^2$-by-$n^2$ matrix). The running time is $n^5$ which is close to linear in the input size $n^4$. We also obtain algorithms with similar running time to learn sparsely-used orthogonal dictionaries even when feature representations have constant relative sparsity and non-independent coordinates. The only previous polynomial-time algorithms to solve these problem are based on solving large semidefinite programs. In contrast, our algorithms are easy to implement directly and are based on spectral projections and tensor-mode rearrangements. Or work is inspired by recent of Hopkins, Schramm, Shi, and Steurer (STOC’16) that shows how fast spectral algorithms can achieve the guarantees of SOS for average-case problems. In this work, we introduce general techniques to capture the guarantees of SOS for worst-case problems.

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.

We propose an efficient meta-algorithm for Bayesian inference problems based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constructions for sum-of-squares and related to the method of moments. Our focus is on sample complexity bounds that are as tight as possible (up to additive lower-order terms) and often achieve statistical thresholds or conjectured computational thresholds. Our algorithm recovers the best known bounds for partial recovery in the stochastic block model, a widely-studied class of inference problems for community detection in graphs. We obtain the first partial recovery guarantees for the mixed-membership stochastic block model (Airoldi et el.) for constant average degree-up to what we conjecture to be the computational threshold for this model. We show that our algorithm exhibits a sharp computational threshold for the stochastic block model with multiple communities beyond the Kesten-Stigum bound-giving evidence that this task may require exponential time. The basic strategy of our algorithm is strikingly simple: we compute the best-possible low-degree approximation for the moments of the posterior distribution of the parameters and use a robust tensor decomposition algorithm to recover the parameters from these approximate posterior moments.

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 𝒲.

We give new algorithms based on the sum-of-squares method for tensor decomposition. Our results improve the best known running times from quasi-polynomial to polynomial for several problems, including decomposing random overcomplete 3-tensors and learning overcomplete dictionaries with constant relative sparsity. We also give the first robust analysis for decomposing overcomplete 4-tensors in the smoothed analysis model. A key ingredient of our analysis is to establish small spectral gaps in moment matrices derived from solutions to sum-of-squares relaxations. To enable this analysis we augment sum-of-squaresrelaxations with spectral analogs of maximum entropy constraints.

We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. For both problems, the best known guarantees are based on the sum-of-squares method. We develop new algorithms inspired by analyses of the sum-of-squares method. Our algorithms achieve the same or similar guarantees as sum-of-squares for these problems but the running time is significantly faster.

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.

We study a statistical model for the \emphtensor principal component analysis problem introduced by Montanari and Richard: Given a order-3 tensor \mathbf T of the form \mathbf T = τ⋅v_0^⊗3 + \mathbf A, where τ≥0 is a signal-to-noise ratio, v_0 is a unit vector, and \mathbf A is a random noise tensor, the goal is to recover the planted vector v_0. For the case that \mathbf A has iid standard Gaussian entries, we give an efficient algorithm to recover v_0 whenever τ≥ω(n^3/4 \log(n)^1/4), and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of \mathbf A. The previous best algorithms with provable guarantees required τ≥Ω(n). In the regime τ≤o(n), natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down. To go beyond this barrier, we use convex relaxations based on the sum-of-squares method. Our recovery algorithm proceeds by rounding a degree-4 sum-of-squares relaxations of the maximum-likelihood-estimation problem for the statistical model. To complement our algorithmic results, we show that degree-4 sum-of-squares relaxations break down for τ≤O(n^3/4/\log(n)^1/4), which demonstrates that improving our current guarantees (by more than logarithmic factors) would require new techniques or might even be intractable. Finally, we show how to exploit additional problem structure in order to solve our sum-of-squares relaxations, up to some approximation, very efficiently. Our fastest algorithm runs in nearly-linear time using shifted (matrix) power iteration and has similar guarantees as above. The analysis of this algorithm also confirms a variant of a conjecture of Montanari and Richard about singular vectors of tensor unfoldings.

We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown n x m matrix A (for m ≥ n) from examples of the form [y = Ax + e,] where x is a random vector in Rm with at most τ m nonzero coordinates, and e is a random noise vector in Rn with bounded magnitude. For the case m=O(n), our algorithm recovers every column of A within arbitrarily good constant accuracy in time mO(log m/log(τ-1)), in particular achieving polynomial time if τ = m-δ for any δ>0, and time mO(log m) if τ is (a sufficiently small) constant. Prior algorithms with comparable assumptions on the distribution required the vector $x$ to be much sparser---at most √n nonzero coordinates---and there were intrinsic barriers preventing these algorithms from applying for denser x.

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than 2nδ, for some constant δ > 0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.

Subexponential time approximation algorithms are presented for the U nique G ames and S mall -S et E xpansion problems. Specifically, for some absolute constant c , the following two algorithms are presented. (1) An exp( kn ϵ )-time algorithm that, given as input a k -alphabet unique game on n variables that has an assignment satisfying 1-ϵ c fraction of its constraints, outputs an assignment satisfying 1-ϵ fraction of the constraints. (2) An exp( n ϵ /δ)-time algorithm that, given as input an n -vertex regular graph that has a set S of δ n vertices with edge expansion at most ϵ c , outputs a set S' of at most δ n vertices with edge expansion at most ϵ. subexponential algorithm is also presented with improved approximation to M ax C ut , S parsest C ut , and V ertex C over on some interesting subclasses of instances. These instances are graphs with low threshold rank , an interesting new graph parameter highlighted by this work. Khot's Unique Games Conjecture (UGC) states that it is NP -hard to achieve approximation guarantees such as ours for U nique G ames . While the results here stop short of refuting the UGC, they do suggest that U nique G ames are significantly easier than NP -hard problems such as M ax 3-S at , M ax 3- Lin , L abel C over , and more, which are believed not to have a subexponential algorithm achieving a nontrivial approximation ratio. Of special interest in these algorithms is a new notion of graph decomposition that may have other applications. Namely, it is shown for every ϵ >0 and every regular n -vertex graph G , by changing at most δ fraction of G 's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most n ϵ eigenvalues larger than 1-η, where η depends polynomially on ϵ. The subexponential algorithm combines this decomposition with previous algorithms for U nique G ames on graphs with few large eigenvalues [Kolla and Tulsiani 2007; Kolla 2010].

The long code is a central tool in hardness of approximation, especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: (1) For any $\varepsilon>0$, we show the existence of an $n$-vertex graph $G$ where every set of $o(n)$ vertices has expansion $1-\varepsilon$, but $G$'s adjacency matrix has more than $\exp(\log^{\delta}n)$ eigenvalues larger than $1-\varepsilon$, where $\delta$ depends only on $\varepsilon$. This answers an open question of Arora, Barak, and Steurer [Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563--572], who asked whether one can improve over the noise graph on the Boolean hypercube that has ${\rm poly}(\log n)$ such eigenvalues. (2) A gadget that reduces Unique Games instances with linear constraints modulo $K$ into instances with alphabet $k$ with a blowup of $k^{{\rm polylog}(K)}$, improving over the previously known gadget with blowup of $k^{\Omega(K)}$. (3) An $n$-variable integrality gap for Unique Games that survives $\exp({\rm poly}(\log\log n))$ rounds of the semidefinite programming version of the Sherali--Adams hierarchy, improving on the previously known bound of ${\rm poly}(\log\log n)$. We show a connection between the local testability of linear codes and Small-Set Expansion in certain related Cayley graphs and use this connection to derandomize the noise graph on the Boolean hypercube.

A direct product function is a function of the form g(x1, ⋯, xk)=(g1(x1), ⋯, g(xk)). We show that the direct product property is locally testable with two queries, that is, a canonical two-query test distinguishes between direct product functions and functions that are far from direct products with constant probability. This local testing question comes up naturally in the context of PCPs, where direct products play a prominent role for gap amplification. We consider the following natural two query test for a given function f:[N]k→[M]kTwo query direct product test: Choose x, y that agree on a random set A of t coordinates and accept if f(x)A=f(y)A. We provide a comprehensive analysis of this test for all parameters N, M, k, t≤O(k) and success probability δ>0. Our main result is that if a given function f:[N]k→[M]kpasses the test with probability δ≥1-ε then there is a direct product function g such that P[f(x)=g(x)]≥1-O(ε). This is the first result relating success in the above (or any) test to the fraction of the domain on which f is equal to a direct product function. This test has been analyzed in previous works for the case t≪k≪N, and results show closeness of f to a direct product under a less natural measure of "approximate agreement". In the small soundness regime, we prove that if the test above passes with probability δ ≥ exp(-k), then the function agrees with a direct product function on local parts of the domain. This extends the previous range of parameters of δ≥exp(-3√k) to the entire meaningful range of δ>exp(-k).

We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game G of entangled value 1 - εc)k), for some universal constant c ≥ 1. Previously parallel repetition with an exponential decay in k was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call “vector quantum strategy” to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our “quantum correlated sampling lemma” generalizes results of van Dam and Hayden on universal embezzlement to the following approximate scenario: two isolated parties, given classical descriptions of arbitrary bipartite states |ψ〉, |φ〉 respectively such that |ψ〉 ≈ |φ〉, are able to locally generate a joint entangled state|Ψ〉 ≈ |ψ〉 ≈ |φ〉 using an initial entangled state that is independent of their inputs.

We study the computational power of general symmetric relaxations for combinatorial optimization problems, both in the linear programming (LP) and semidefinite programming (SDP) case. We show new connections to explicit LP and SDP relaxations, like those obtained from standard hierarchies. Concretely, for kkn) achieve best-possible k approximation guarantees for Max CSPs among all symmetric SDP relaxations of size at most (kn). This result gives the first k lower bounds for symmetric SDPrelaxations of Max CSPs, and indicates that the sum-of-squares method provides the “right” SDP relaxation for this class of problems. Moreover, for k2k) for the traveling salesman problem that achieve per instance best-possible approximation (kn).

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a combining algorithm---an algorithm that maps a distribution over solutions into a (possibly weaker) solution---into a rounding algorithm that maps a solution of the relaxation to a solution of the original problem.

We propose an analytical framework for studying parallel repetition, a basic product operation for one-round twoplayer games. In this framework, we consider a relaxation of the value of projection games. We show that this relaxation is multiplicative with respect to parallel repetition and that it provides a good approximation to the game value. Based on this relaxation, we prove the following improved parallel repetition bound: For every projection game G with value at most ρ, the k-fold parallel repetition G⊗k has value at most

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for MAX CUT has an integrality gap of 1/2 and any such linear program for MAX 3-SAT has an integrality gap of 7/8.

This work studies several questions about the optimality of semidefinite programming (SDP) for constraint satisfaction problems (CSPs). First we propose the hypothesis that the well known Basic SDP relaxation is actually optimal for random instances of constraint satisfaction problems for every predicate. This unifies several conjectures proposed in the past, and suggests a unifying principle for the average-case complexity of CSPs. We provide several types of indirect evidence for the truth of this hypothesis, and also show that it (and its variants) imply several conjectures in hardness of approximation including polynomial factor hardness for the densest k subgraph problem and hard instances for the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell (1993).

The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique Games Conjecture (Raghavendra, Steurer, STOC 2010). Our main result is that the Small-Set Expansion Hypothesis is in fact equivalent to a variant of the Unique Games Conjecture. More precisely, the hypothesis is equivalent to the Unique Games Conjecture restricted to instance with a fairly mild condition on the expansion of small sets. Alongside, we obtain the first strong hardness of approximation results for the Balanced Separator and Minimum Linear Arrangement problems. Before, no such hardness was known for these problems even assuming the Unique Games Conjecture. These results not only establish the Small-Set Expansion Hypothesis as a natural unifying hypothesis that implies the Unique Games Conjecture, all its consequences and, in addition, hardness results for other problems like Balanced Separator and Minimum Linear Arrangement, but our results also show that the Small-Set Expansion Hypothesis problem lies at the combinatorial heart of the Unique Games Conjecture. The key technical ingredient is a new way of exploiting the structure of the Unique Games instances obtained from the Small-Set Expansion Hypothesis via (Raghavendra, Steurer, 2010). This additional structure allows us to modify standard reductions in a way that essentially destroys their local-gadget nature. Using this modification, we can argue about the expansion in the graphs produced by the reduction without relying on expansion properties of the underlying Unique Games instance (which would be impossible for a local-gadget reduction).

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1) For any ε >; 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - ε, but G's adjacency matrix has more than exp(logδn) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2) A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of Kpolylog(K), improving over the previously known gadget with blowup of 2Ω(K). 3) An n variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.

We develop a framework for proving approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that quadratic approximations for CLIQUE require linear programs of exponential size. (This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem) Moreover, we establish a similar result for approximations of semi definite programs by linear programs. Our main technical ingredient is a quantitative improvement of Razborov's rectangle corruption lemma (1992) for the high error regime, which gives strong lower bounds on the nonnegative rank of certain perturbations of the unique disjoint ness matrix.

We study the computational complexity of approximating the 2-to-q norm of linear operators (defined as |A|2->q = maxv≠ 0|Av|q/|v|2) for q > 2, as well as connections between this question and issues arising in quantum information theory and the study of Khot's Unique Games Conjecture (UGC). We show the following: For any constant even integer q ≥ 4, a graph G is a small-set expander if and only if the projector into the span of the top eigenvectors of G's adjacency matrix has bounded 2->q norm. As a corollary, a good approximation to the 2->q norm will refute the Small-Set Expansion Conjecture --- a close variant of the UGC. We also show that such a good approximation can be obtained in exp(n2/q) time, thus obtaining a different proof of the known subexponential algorithm for Small-Set-Expansion. Constant rounds of the "Sum of Squares" semidefinite programing hierarchy certify an upper bound on the 2->4 norm of the projector to low degree polynomials over the Boolean cube, as well certify the unsatisfiability of the "noisy cube" and "short code" based instances of Unique-Games considered by prior works. This improves on the previous upper bound of exp(logO(1) n) rounds (for the "short code"), as well as separates the "Sum of Squares"/"Lasserre" hierarchy from weaker hierarchies that were known to require ω(1) rounds. We show reductions between computing the 2->4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are: (i) the 2->4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension, (ii) the 2->4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(√n poly log(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2->4 norm.

Linear programming (LP) decoding for low-density parity-check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance-coming close to that of iterative decoding algorithms-and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05 fraction of correctable errors for rate-½ codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.

We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the in- put graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every 2-CSP instance 3, a rounding algorithm for r rounds of the Lasserre SDP hierarchy for 3 that obtains an integral solution which is at most ε worse than the relaxation's value (normalized to lie in [0, 1]), as long as r >; k·rank≥θ(3)/ poly(ε), where k is the alphabet size of J, θ = poly(ε/k), and rank≥θ(J) denotes the number of eigenvalues larger than θ in the normalized adjacency matrix of the constraint graph of J. In the case that J is a Unique Games instance, the threshold θ is only a polynomial in ε, and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for every instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the nolO(r)constraints specified by the rthlevel of the Lasserre hierarchy, and in some cases r rounds of our program can be evaluated in time 2O(r)poly(n).

We initiate a study of when the value of mathematical relaxations such as linear and semi-definite programs for constraint satisfaction problems (CSPs) is approximately preserved when restricting the instance to a sub-instance induced by a small random subsample of the variables. Let C be a family of CSPs such as 3SAT, Max-Cut, etc., and let П be a mathematical program that is a relaxation for C, in the sense that for every instance P ∊ C, П(P) is a number in [0, 1] upper bounding the maximum fraction of satisfiable constraints of P. Loosely speaking, we say that subsampling holds for C and П if for every sufficiently dense instance P ∊ C and every ε > 0, if we let P′ be the instance obtained by restricting P to a sufficiently large constant number of variables, then П(P′) ∊ (1 ± ε)П(P). We say that weak subsampling holds if the above guarantee is replaced with П(P′) = 1 − Θ(γ) whenever П(P) = 1 − γ, where Θ hides only absolute constants. We obtain both positive and negative results, showing that: 1. Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP is a variant of the semi-definite program considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every constraint-satisfaction problem under the unique games conjecture. BasicLP is the linear programming analog of BasicSDP. 2. For tighter versions of BasicSDP obtained by adding additional constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type. 3. There are non-unique CSPs for which even weak subsampling fails for the above tighter semi-definite programs. Also there are unique CSPs for which (even weak) subsampling fails for the Sherali-Adams linear programming hierarchy. As a corollary of our weak subsampling for strong semi-definite programs, we obtain a polynomial-time algorithm to certify that random geometric graphs (of the type considered by Feige and Schechtman, 2002) of max-cut value 1 − γ have a cut value at most 1 − γ/10. More generally, our results give an approach to obtaining average-case algorithms for CSPs using semi-definite programming hierarchies.

We give a subexponential time approximation algorithm for the Unique Games problem. The algorithms run in time that is exponential in an arbitrarily small polynomial of the input size, nε. The approximation guarantee depends on ε, but not on the alphabet size or the number of variables. We also obtain a subexponential algorithms with improved approximations for SMALL-SET EXPANSION and MULTICUT. For MAX CUT, SPARSEST CUT, and VERTEX COVER, we give subexponential algorithms with improved approximations on some interesting subclasses of instances. Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for the Unique Games. While our results stop short of refuting the UGC, they do suggest that Unique Games is significantly easier than NP-hard problems such as MAX 3SAT, MAX 3LIN, Label Cover and more, that are believed not to have a subexponential algorithm achieving a non-trivial approximation ratio. The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every ε > 0 and every regular n-vertex graph G, by changing at most ε fraction of G's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most nεeigenvalues larger than 1 - η, where η depends polynomially on ε.

The class of constraint satisfactions problems (CSPs) captures many fundamental combinatorial optimization problems such as Max Cut, Max q-Cut, Unique Games, and Max k-Sat. Recently, Raghavendra (STOC'08) identified a simple semidefinite programming relaxation that gives the best possible approximation for any CSP, assuming the Unique Games Conjecture. Raghavendra and Steurer (FOCS'09) showed that, independent of the truth of the Unique Games Conjecture, the integrality gap of this relaxation cannot be improved even by adding a large class of valid inequalities.

The edge expansion of a subset of vertices S ⊆ V in a graph G measures the fraction of edges that leave S. In a d-regular graph, the edge expansion/conductance Φ(S) of a subset S ⊆ V is defined as Φ(S) = (|E(S, V\S)|)/(d|S|). Approximating the conductance of small linear sized sets (size δ n) is a natural optimization question that is a variant of the well-studied Sparsest Cut problem. However, there are no known algorithms to even distinguish between almost complete edge expansion (Φ(S) = 1-ε), and close to 0 expansion. In this work, we investigate the connection between Graph Expansion and the Unique Games Conjecture. Specifically, we show the following: We show that a simple decision version of the problem of approximating small set expansion reduces to Unique Games. Thus if approximating edge expansion of small sets is hard, then Unique Games is hard. Alternatively, a refutation of the UGC will yield better algorithms to approximate edge expansion in graphs. This is the first non-trivial "reverse" reduction from a natural optimization problem to Unique Games. Under a slightly stronger UGC that assumes mild expansion of small sets, we show that it is UG-hard to approximate small set expansion. On instances with sufficiently good expansion of small sets, we show that Unique Games is easy by extending the techniques of [4].

The spectral profile of a graph is a natural generalization of the classical notion of its Rayleigh quotient. Roughly speaking, given a graph G, for each 0< δ < 1, the spectral profile ΛG(δ) minimizes the Rayleigh quotient (from the variational characterization) of the spectral gap of the Laplacian matrix of G over vectors with support at most δ over a suitable probability measure. Formally, the spectral profile ΛG of a graph G is a function ΛG : [0,1/2] -> R defined as: ΛG(δ) def= minx∈ RVd(supp(x))≤ δ (∑gij (xi-xj)2)/(∑i di xi2) where gij is the weight of the edge (i,j) in the graph, di is the degree of vertex i, and d(\supp(x)) is the fraction of edges incident on vertices within the support of vector x. While the notion of the spectral profile has numerous applications in Markov chain, it is also is closely tied to its isoperimetric profile of a graph. Specifically, the spectral profile is a relaxation for the problem of approximating edge expansion of small sets in graphs. In this work, we obtain an efficient algorithm that yields a log(1/δ)-factor approximation for the value of ΛG(δ). By virtue of its connection to edge-expansion, we also obtain an algorithm for the problem of approximating edge expansion of small linear sized sets in a graph. This problem was recently shown to be intimately connected to the Unique Games Conjecture in [18]. Finally, we extend the techniques to obtain approximation algorithms with similar guarantees for restricted eigenvalue problems on diagonally dominant matrices.

With the work of Khot and Vishnoi as a starting point, we obtain integrality gaps for certain strong SDP relaxations of Unique Games. Specifically, we exhibit a Unique Games gap instance for the basic semidefinite program strengthened by all valid linear inequalities on the inner products of up to exp(¿(log log n)1/4) vectors. For a stronger relaxation obtained from the basic semidefinite program by R rounds of Sherali-Adams liftand-project, we prove a Unique Games integrality gap for R = ¿(log log n)1/4. By composing these SDP gaps with UGC-hardness reductions, the above results imply corresponding integrality gaps for every problem for which a UGC-based hardness is known. Consequently, this work implies that including any valid constraints on up to exp(¿(log log n)1/4) vectors to natural semidefinite program, does not improve the approximation ratio for any problem in the following classes: constraint satisfaction problems, ordering constraint satisfaction problems and metric labeling problems over constant-size metrics. We obtain similar SDP integrality gaps for Balanced Separator, building on. We also exhibit, for explicit constants ¿, ¿ > 0, an n-point negative-type metric which requires distortion ¿(log log n)¿to embed into ¿1, although all its subsets of size exp(¿(log log n)¿) embed isometrically into ¿1.

A large number of interesting combinatorial optimization problems like MAX CUT, MAX k-SAT, and UNIQUE GAMES fall under the class of constraint satisfaction problems (CSPs). Recent work by one of the authors (STOC 2008) identifies a semidefinite programming (SDP) relaxation that yields the optimal approximation ratio for every CSP, under the Unique Games Conjecture (UGC). Very recently (FOCS 2009), the authors also showed unconditionally that the integrality gap of this basic SDP relaxation cannot be reduced by adding large classes of valid inequalities (e.g., in the fashion of Sherali-Adams LP hierarchies). In this work, we present an efficient rounding scheme that achieves the integrality gap of this basic SDP relaxation for every CSP (and it also achieves the gap of much stronger SDP relaxations). The SDP relaxation we consider is stronger or equivalent to any relaxation used in literature to approximate CSPs. Thus, irrespective of the truth of the UGC, our work yields an efficient generic algorithm that for every CSP, achieves an approximation at least as good as the best known algorithm in literature. The rounding algorithm in this paper can be summarized succinctly as follows: Reduce the dimension of SDP solution by random projection, discretize the projected vectors, and solve the resulting CSP instance by brute force! Even the proof is simple in that it avoids the use of the machinery from unique games reductions such as dictatorship tests, Fourier analysis or the invariance principle. A common theme of this paper and the subsequent paper in the same conference is a robustness lemma for SDP relaxations which asserts that approximately feasible solutions can be made feasible by "smoothing'' without changing the objective value significantly.

The Grothendieck constant KG is the smallest constant such that for every d ∊ ℕ and every matrix A = (aij), where B(d) is the unit ball in ℝd. Despite several efforts [15, 23], the value of the constant KG remains unknown. The Grothendieck constant KG is precisely the integrality gap of a natural SDP relaxation for the KM,N-Quadratic Programming problem. The input to this problem is a matrix A = (αij) and the objective is to maximize the quadratic form Σij aijxiyj over xi, yj ∊ [–1, 1]. In this work, we apply techniques from [22] to the KM,N-Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the KM,N-Quadratic Programming problem to any factor better than the Grothendieck constant KG. By adapting a “bootstrapping” argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results: An approximation algorithm for KM,N-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant KG (optimal approximation ratio assuming the Unique Games Conjecture). We show that the Grothendieck constant KG can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η-close to the Grothendieck constant. We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.

Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance --coming close to that of iterative decoding algorithms--- and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between LP decoding and message passing algorithms.

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically,denoting by val(G) the value of a two-prover unique game G, andby sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every l epsi N, if sdpval(G) ges 1-delta, then val(Gl) ges 1-radicsldelta. Here, Gldenotes the l-fold parallel repetition of G, and s=O(log(k/delta)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i.e., k=2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log(1/delta)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(Gl) may be much larger than val(G)l, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS'08) has shown such an example using the max-cut game on oddcycles. Our results are based on a generalization of his techniques.

We present an efficient algorithm to find a good solution to the Unique Games problem when the constraint graph is an expander.

The edge coloring problem considers the assignment of colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. We give polynomial time algorithms for approximate edge coloring of multigraphs, that is, parallel edges are allowed. The best previous algorithms achieve a fixed constant approximation factor plus a small additive offset. One of our algorithms achieves solution quality opt + √9opt/2 and has execution time polynomial in the number of nodes and the logarithm of the maximum edge multiplicity.

Many load balancing problems that arise in scientific computing applications ask to partition a graph with weights on the vertices and costs on the edges into a given number of almost equally-weighted parts such that the maximum boundary cost over all parts is small.Here, this partitioning problem is considered for boundeddegree graphs G ≡ (V,E) with edge costs c: E → R+ that have a p-separator theorem for some p > 1, i.e., any (arbitrarily weighted) subgraph of G can be separated into two parts of roughly the same weight by removing separator S⊆V such that the edges incident to S in the subgraph have total cost at most proportional to (Εecp e)1/p, where the sum is over all edges in the subgraph.We show for all positive integers k and weights w that the vertices of G can be partitioned into k parts such that the weight of each part differs from the average weight Εv∈V wv k by less than maxv∈V wv, and the boundary edges of each part have cost at most proportional to (Εe∈ cp e/k)1/p + maxe∈E ce. The partition can be computed in time nearly proportional to the time for computing a separator S of G.Our upper bound on the boundary costs is shown to be tight up to a constant factor for infinitely many instances with a broad range of parameters. Previous results achieved this bound only if one has c ≡ 1, w ≡ 1, and one allows parts with weight exceeding the average by a constant fraction.