Pravesh K. Kothari

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 the hypothesis of Dinur et. al. follows from a conjecture we call the "Inverse Shortcode Hypothesis" characterizing the non-expanding sets of the degree-two shortcode 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 "Inverse Shortcode 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. Moreover, we believe that the shortcode graph provides a useful view of both the hypothesis and the reduction, and might be useful in extending it further.

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our 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, outlier-robust algorithms for independent component analysis and learning mixtures of Gaussians.

Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem: Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample.

We develop a new scheme of convex relaxations for \( k \)-means clustering based on sum-of-squares norms, a relaxation of the injective tensor norm that is efficiently computable using the Sum-of-Squares algorithm. We give an algorithm based on this relaxation that recovers a faithful approximation to the true means in the given data whenever the low-degree moments of the points in each cluster have bounded in (sos relaxations of) injective tensor norms.
We then prove a sharp upper bound on the sum-of-squares relaxations of injective tensors norms for moment tensors of any distribution that satisfy the Poincare inequality . The Poincare inequality is intensely investigated in probability theory, and a large class of random variables satisfy it including all rando variables with distributions that are arbitrary product or strongly log-concave including well-studied examples such as gaussians, and any sum or continuous transformation of such distributions.
As an immediate corollary, for any \( \gamma > 0 \), we obtain an efficient algorithm for learning the means of a mixture of \( k \) arbitrary Poincare distributions so long as the means have dimension-independent separation \( \Omega(k^{\gamma}) \). This in particular yields an algorithm for learning spherical Gaussian mixtures with dimension-independent separation \( \Omega(k^{\gamma}) \), thus partially resolving an open problem recently posed by Regev and Vijayaraghavan (FOCS 2017).
Our algorithm further works even in the robust setting where an \( \varepsilon \) fraction of arbitrary outliers are added to the data, as long as the fraction of outliers is smaller than the smallest cluster. We therefore obtain results in the strong agnostic setting where, in addition to not knowing the distribution family, the data itself may be arbitrarily corrupted.

An \( m \) output pseudorandom generator \( G\colon (\on^b)^n \rightarrow \on^m \) that takes input \( n \) blocks of \( b \) bits each is said to be \( \ell \)-block local if every output is a function of at most \( \ell \) blocks. We show that such \( \ell \)-block local pseudorandom generators can have output length at most \( \tilde{O}(2^{\ell b} n^{\lceil \ell/2 \rceil}) \), by presenting a polynomial time algorithm that distinguishes inputs of the form \( G(x) \) from inputs where each coordinate is sampled from the uniform distribution on \( m \) bits.
As a corollary, we refute some conjectures recently made in the context of constructing provably secure indistinguishability obfuscation (iO). This includes refuting the assumptions underlying Lin and Tessaro's (2017) recently proposed candidate iO from bilinear maps. Specifically, they assumed the existence of a secure pseudorandom generator \( G:\colon \{ \pm 1 \}^{nb} \rightarrow \on^{2^{cb}n} \) as above for large enough \( c>3 \) and \( \ell=2 \). (Following this work, and an independent work of Lombardi and Vaikuntanthan (2017), Lin and Tessaro retracted the bilinear maps based candidate from their manuscript.)
Our results actually hold for the much wider class of low-degree, non-binary valued pseudorandom generators: if every output of \( G\colon\pmset^n \rightarrow \R^m \) (\( \mathbb{R} \) = reals) is a polynomial (over \( \mathbb{R} \)) of degree at most \( d \) with at most \( s \) monomials and \( m \ge \tilde{\Omega}(sn^{\lceil d/2 \rceil}) \), then there is a polynomial time algorithm for distinguishing the output \( G(x) \) from \( z \) where each coordinate \( z_i \) is sampled independently from the marginal distribution on \( G_i \). Furthermore, our results continue to hold under arbitrary pre-processing of the seed. This implies that any such map \( G \), with arbitrary seed pre-processing, cannot be a pseudorandom generator in the mild sense of fooling a product distribution on the output space. This allows us to rule out various natural modifications to the notion of generators suggested in other works that still allow obtaining indistinguishability obfuscation from bilinear maps.
Our algorithms are based on the Sum of Squares (SoS) paradigm, and in most cases can even be defined more simply using a canonical semidefinite program. We complement our algorithm by presenting a class of candidate generators with block-wise locality \( 3 \) and constant block size, that resists both Gaussian elimination and sum of squares (SOS) algorithms whenever \( m = n^{1.5-\epsilon} \). This class is extremely easy to describe: Let \( \mathbb{G} \) be any simple non-abelian group with the group operation ``\( \ast \)'', and interpret the blocks of \( x \) as elements in \( \mathbb{G} \). The description of the pseudorandom generator is a sequence of \( m \) triples of indices \( (i,j,k) \) chosen at random and each output of the generator is of the form \( x_i \ast x_j \ast x_k \).

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-\( k \)-subgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-$d$ matrix polynomials are as powerful as SoS semidefinite programs of size roughly \( n^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 low-degree matrix polynomials (and inspired by recent work on SoS and the planted clique problem (Barak-Hopkins-Kelner-Kothari-Moitra-Potechin 2016), we prove new nearly-tight SoS lower bounds for the tensor and sparse principal component analysis problems. Our lower bounds are the first to suggest that improving upon the signal-to-noise ratios handled by existing polynomial-time algorithms for these problems may require subexponential time.

For every \( \epsilon>0 \), we give an \( \exp(\tilde{O}(\sqrt{n}/\epsilon^2)) \)-time algorithm for the \( 1 \) vs \( 1-\epsilon \) Best Separable State (BSS) problem of distinguishing, given an \( n^2\times n^2 \) matrix \( \cM \) corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state \( \rho \) that \( \cM \) accepts with probability \( 1 \), and the case that every separable state is accepted with probability at most \( 1-\epsilon \). Equivalently, our algorithm takes the description of a subspace \( \mathcal{W} \subseteq \mathbb F^{n^2} \) (where \( \mathbb F \) can be either the real or complex field) and distinguishes between the case that \( \mathcal{W} \) contains a rank one matrix, and the case that every rank one matrix is at least \( \epsilon \) far (in \( \ell_2 \) distance) from \( \mathcal{W} \). 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 \( \tilde{O}(\sqrt{n}) \).

Let \( P:\{0,1\}^k \to \{0,1\} \) be a nontrivial \( k \)-ary predicate. Consider a random instance of the constraint satisfaction problem \( CSP(P) \) on \( n \) variables with \( \Delta n \) constraints, each being \( P \) applied to \( k \) randomly chosen literals. Provided the constraint density satisfies \( \Delta \gg 1 \), such an instance is unsatisfiable with high probability. The refutation problem asks to efficiently find a proof of unsatisfiability. We show that whenever the predicate \( P \) supports a \( t \)- wise uniform probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree \( d = \Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta}) \) (which runs in time \( n^{O(d)} \) cannot refute a random instance of \( CSP(P) \). In particular, the polynomial-time SOS algorithm requires \( \tilde{\Omega}(n^{(t+1)/2}) \) constraints to refute random instances of CSP(P) when \( P \) supports a \( t \)-wise uniform distribution on its satisfying assignments. More generally, we consider the \( \delta \)-refutation problem, in which the goal is to certify that at most a \( (1-\delta) \)-fraction of constraints can be simultaneously satisfied. We show that if \( P \) is \( \delta \)-close to supporting a \( t \)-wise uniform distribution on satisfying assignments, then the degree-\( \Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta}) \) SOS algorithm cannot \( (\delta+o(1)) \)-refute a random instance of CSP(P). This is the first result to show a distinction between the degree SOS needs to solve the refutation problem and the degree it needs to solve the harder \( \delta \)-refutation problem. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate \(P\), they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen-O'Donnell-Witmer (STOC 2015) and Raghavendra-Rao-Schramm (STOC 2016), this full three-way tradeoff is tight , up to lower-order factors.

We show that for constraint satisfaction problems (CSPs), weakly-exponential size linear programming relaxations are as powerful as \( n^{\Omega(1)} \)-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly-exponential improvement over previous results; previously, it was only known that linear programs of size \( n^{o(\log n)}\) cannot beat random guessing for any CSP (Chan-Lee-Raghavendra-Steurer 2013). Our bounds are obtained by exploiting and extending the recent progress in communication complexity for "lifting" query lower bounds to communication problems. The main ingredient in our results is a new structural result on ``high-entropy rectangles'' that may of independent interest in communication complexity.

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

The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size \( \omega \gg \log{(n)} \) added to an Erdős–Rényi graph \( G \sim G(n,1/2) \), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size \( \omega = \tilde{\Omega}(n^{1/2}) \). By contrast, information theoretically, one can recover planted cliques so long as \( \omega \gg \log{(n)} \). In this work, we continue the investigation of algorithms from the sum of squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson (MPW, 2015) and Deshpande and Montanari (DM,2015). Our main results improve upon both these previous works by showing: 1. Degree four SoS does not recover the planted clique unless \( \omega \gg n^{1/2}/ poly \log{(n)} \), improving upon the bound \( \omega \gg n^{1/3} \) due to DM. A similar result was obtained independently by Raghavendra and Schramm (2015). 2. For \( 2 < d = o(\sqrt{log{(n)}}) \), degree 2d SoS does not recover the planted clique unless \( \omega \gg n^{\frac{1}{d+1}}/2^d poly \log{(n)} \), improving upon the bound due to MPW. Our proof for the second result is based on a fine spectral analysis of the certificate used in the prior works MPW,DM and Feige and Krauthgamer (2003) by decomposing it along an appropriately chosen basis. Along the way, we develop combinatorial tools to analyze the spectrum of random matrices with dependent entries and to understand the symmetries in the eigenspaces of the set symmetric matrices inspired by work of Grigoriev (2001). An argument of Kelner shows that the first result cannot be proved using the same certificate. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by "correcting" the certificate of previous works.

Owing to several applications in large scale learning and vision problems, fast submodular function minimization (SFM) has become a critical problem. Theoretically, unconstrained SFM can be performed in polynomial time [Iwata-Fujishige-Fleisher 2001, Iwata-Orlin 2009]. However, these algorithms are typically not practical. In 1976, Wolfe proposed an algorithm to find the minimum Euclidean norm point in a polytope, and in 1980, Fujishige showed how Wolfe's algorithm can be used for SFM. For general submodular functions, this Fujishige-Wolfe minimum norm algorithm seems to have the best empirical performance. Despite its good practical performance, very little is known about Wolfe's minimum norm algorithm theoretically. To our knowledge, the only result is an exponential time analysis due to Wolfe himself. In this paper we give a maiden convergence analysis of Wolfe's algorithm. We prove that in \( t \) iterations, Wolfe's algorithm returns an \( O(1/t) \)-approximate solution to the min-norm point on any polytope. We also prove a robust version of Fujishige's theorem which shows that an \( O(1/n^2)\) -approximate solution to the min-norm point on the base polytope implies exact submodular minimization. As a corollary, we get the first pseudo-polynomial time guarantee for the Fujishige-Wolfe minimum norm algorithm for unconstrained submodular function minimization.