Arrow Research search

Author name cluster

David Steurer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

45 papers
2 author rows

Possible papers

45

FOCS Conference 2025 Conference Paper

Finding Colorings in One-Sided Expanders

  • Rares-Darius Buhai
  • Yiding Hua
  • David Steurer
  • Andor Vári-Kakas

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.

Details

NeurIPS Conference 2025 Conference Paper

Low-degree evidence for computational transition of recovery rate in stochastic block model

  • Jingqiu Ding
  • Yiding Hua
  • Lucas Slot
  • David Steurer

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

PDF Details

NeurIPS Conference 2024 Conference Paper

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust

  • Hongjie Chen
  • Jingqiu Ding
  • Yiding Hua
  • David Steurer

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

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Robust Mixture Learning when Outliers Overwhelm Small Groups

  • Daniil Dmitriev
  • Rares-Darius Buhai
  • Stefan Tiegel
  • Alexander Wolters
  • Gleb Novikov
  • Amartya Sanyal
  • David Steurer
  • Fanny Yang

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.

PDF Details DOI

FOCS Conference 2024 Conference Paper

Semirandom Planted Clique and the Restricted Isometry Property

  • Jaroslaw Blasiok
  • Rares-Darius Buhai
  • Pravesh K. Kothari
  • David Steurer

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.

Details

NeurIPS Conference 2023 Conference Paper

Private estimation algorithms for stochastic block models and mixture models

  • Hongjie Chen
  • Vincent Cohen-Addad
  • Tommaso d’Orsi
  • Alessandro Epasto
  • Jacob Imola
  • David Steurer
  • Stefan Tiegel

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.

PDF Details

NeurIPS Conference 2023 Conference Paper

Robust Mean Estimation Without Moments for Symmetric Distributions

  • Gleb Novikov
  • David Steurer
  • Stefan Tiegel

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.

PDF Details

NeurIPS Conference 2021 Conference Paper

Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers

  • Tommaso d'Orsi
  • Chih-Hung Liu
  • Rajai Nasser
  • Gleb Novikov
  • David Steurer
  • Stefan Tiegel

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.

PDF Details

ICML Conference 2021 Conference Paper

Consistent regression when oblivious outliers overwhelm

  • Tommaso d'Orsi
  • Gleb Novikov
  • David Steurer

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.

Details

FOCS Conference 2021 Conference Paper

Robust recovery for stochastic block models

  • Jingqiu Ding
  • Tommaso d'Orsi
  • Rajai Nasser
  • David Steurer

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.

Details

SODA Conference 2021 Conference Paper

SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation

  • David Steurer
  • Stefan Tiegel

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 d O ( ℓ ) · n O (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 d O ( ℓ ).

Details

NeurIPS Conference 2020 Conference Paper

Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks

  • Jingqiu Ding
  • Samuel Hopkins
  • David Steurer

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.

PDF Details

FOCS Conference 2020 Conference Paper

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates

  • Tommaso d'Orsi
  • Pravesh K. Kothari
  • Gleb Novikov
  • David Steurer

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

Details

FOCS Conference 2017 Conference Paper

Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems

  • Samuel B. Hopkins 0001
  • David Steurer

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.

Details

STOC Conference 2017 Conference Paper

Quantum entanglement, sum of squares, and the log rank conjecture

  • Boaz Barak
  • Pravesh K. Kothari
  • David Steurer

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 n 2 x n 2 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 𝒲 ⊆ 𝔽 n 2 (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 𝒲. To the best of our knowledge, this is the first improvement over the brute-force exp( n )-time algorithm for this problem. Our algorithm is based on the sum-of-squares hierarchy and its analysis is inspired by Lovett's proof (STOC '14, JACM '16) that the communication complexity of every rank- n Boolean matrix is bounded by Õ(√ n ).

Details

FOCS Conference 2017 Conference Paper

The Power of Sum-of-Squares for Detecting Hidden Structures

  • Samuel B. Hopkins 0001
  • Pravesh K. Kothari
  • Aaron Potechin
  • Prasad Raghavendra
  • Tselil Schramm
  • David Steurer

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.

Details

STOC Conference 2016 Conference Paper

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

  • Samuel B. Hopkins 0001
  • Tselil Schramm
  • Jonathan Shi
  • David Steurer

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. For the planted sparse vector problem, we give an algorithm with running time nearly linear in the input size that approximately recovers a planted sparse vector with up to constant relative sparsity in a random subspace of ℝ n of dimension up to Ω(√ n ). These recovery guarantees match the best known ones of Barak, Kelner, and Steurer (STOC 2014) up to logarithmic factors. For tensor decomposition, we give an algorithm with running time close to linear in the input size (with exponent ≈ 1.125) that approximately recovers a component of a random 3-tensor over ℝ n of rank up to Ω( n 4/3 ). The best previous algorithm for this problem due to Ge and Ma (RANDOM 2015) works up to rank Ω( n 3/2 ) but requires quasipolynomial time.

Details

FOCS Conference 2016 Conference Paper

Polynomial-Time Tensor Decompositions with Sum-of-Squares

  • Tengyu Ma 0001
  • Jonathan Shi
  • David Steurer

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.

Details

STOC Conference 2015 Conference Paper

Lower Bounds on the Size of Semidefinite Programming Relaxations

  • James R. Lee
  • Prasad Raghavendra
  • David Steurer

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 2 n δ , for some constant δ > 0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for max-sat.

Details

STOC Conference 2014 Conference Paper

Analytical approach to parallel repetition

  • Irit Dinur
  • David Steurer

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 [EQUATION] This statement implies a parallel repetition bound for projection games with low value ρ . Previously, it was not known whether parallel repetition decreases the value of such games. This result allows us to show that approximating set cover to within factor (1 --- ε ) ln n is NP-hard for every ε > 0, strengthening Feige's quasi-NP-hardness and also building on previous work by Moshkovitz and Raz. In this framework, we also show improved bounds for few parallel repetitions of projection games, showing that Raz's counterexample to strong parallel repetition is tight even for a small number of repetitions. Finally, we also give a short proof for the NP-hardness of label cover(1, δ ) for all δ > 0, starting from the basic PCP theorem.

Details

FOCS Conference 2013 Conference Paper

Approximate Constraint Satisfaction Requires Large LP Relaxations

  • Siu On Chan
  • James R. Lee
  • Prasad Raghavendra
  • David Steurer

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.

Details

FOCS Conference 2012 Conference Paper

Approximation Limits of Linear Programs (Beyond Hierarchies)

  • Gábor Braun
  • Samuel Fiorini
  • Sebastian Pokutta
  • David Steurer

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.

Details

STOC Conference 2012 Conference Paper

Hypercontractivity, sum-of-squares proofs, and their applications

  • Boaz Barak
  • Fernando G. S. L. Brandão
  • Aram W. Harrow
  • Jonathan A. Kelner
  • David Steurer
  • Yuan Zhou 0007

We study the computational complexity of approximating the 2-to-q norm of linear operators (defined as |A| 2->q = max v≠ 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(n 2/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(log O(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.

Details

FOCS Conference 2012 Conference Paper

Making the Long Code Shorter

  • Boaz Barak
  • Parikshit Gopalan
  • Johan Håstad
  • Raghu Meka
  • Prasad Raghavendra
  • David Steurer

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 K polylog(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.

Details

FOCS Conference 2011 Conference Paper

Rounding Semidefinite Programming Hierarchies via Global Correlation

  • Boaz Barak
  • Prasad Raghavendra
  • David Steurer

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 nol O(r) constraints specified by the r th level of the Lasserre hierarchy, and in some cases r rounds of our program can be evaluated in time 2 O(r) poly(n).

Details

SODA Conference 2011 Conference Paper

Subsampling Mathematical Relaxations and Average-case Complexity

  • Boaz Barak
  • Moritz Hardt
  • Thomas Holenstein
  • David Steurer

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.

Details

SODA Conference 2010 Conference Paper

Fast SDP Algorithms for Constraint Satisfaction Problems

  • David Steurer

The class of constraint satisfactions problems (CSPs) captures many fundamental combinatorial optimization problems such as M ax C ut, M ax q -C ut, U nique G ames, and M ax k -S at. 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. We present an algorithm that finds an approximately optimal solution to this relaxation in near-linear time. Combining this algorithm with a rounding scheme of Raghavendra and Steurer (FOCS'09) leads to an approximation algorithm for any CSP that runs in near-linear time and has an approximation guarantee that matches the integrality gap, which is optimal assuming the Unique Games Conjecture.

Details

STOC Conference 2010 Conference Paper

Graph expansion and the unique games conjecture

  • Prasad Raghavendra
  • David Steurer

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

Details

FOCS Conference 2010 Conference Paper

Subexponential Algorithms for Unique Games and Related Problems

  • Sanjeev Arora
  • Boaz Barak
  • David Steurer

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

Details

FOCS Conference 2009 Conference Paper

How to Round Any CSP

  • Prasad Raghavendra
  • David Steurer

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.

Details

FOCS Conference 2009 Conference Paper

Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

  • Prasad Raghavendra
  • David Steurer

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.

Details

SODA Conference 2009 Conference Paper

Towards computing the Grothendieck constant

  • Prasad Raghavendra
  • David Steurer

The Grothendieck constant K G is the smallest constant such that for every d ∊ ℕ and every matrix A = ( a ij ), where B ( d ) is the unit ball in ℝ d. Despite several efforts [15, 23], the value of the constant K G remains unknown. The Grothendieck constant K G is precisely the integrality gap of a natural SDP relaxation for the K M, N -Quadratic Programming problem. The input to this problem is a matrix A = ( α ij ) and the objective is to maximize the quadratic form Σ ij a ij x i y j over x i, y j ∊ [–1, 1]. In this work, we apply techniques from [22] to the K M, 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 K M, N -Q uadratic P rogramming problem to any factor better than the Grothendieck constant K G. 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 K M, N -Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant K G (optimal approximation ratio assuming the Unique Games Conjecture). • We show that the Grothendieck constant K G 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.

Details

FOCS Conference 2008 Conference Paper

Rounding Parallel Repetitions of Unique Games

  • Boaz Barak
  • Moritz Hardt
  • Ishay Haviv
  • Anup Rao 0001
  • Oded Regev 0001
  • David Steurer

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(G l ) ges 1-radicsldelta. Here, G l denotes 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(G l ) 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.

Details