Pravesh K. Kothari

FOCS Conference 2025 Conference Paper

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

• Arpon Basu
• Jun-Ting Hsieh
• Pravesh K. Kothari
• Andrew D. Lin

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

FOCS Conference 2025 Conference Paper

Overcomplete Tensor Decomposition via Koszul-Young Flattenings

• Pravesh K. Kothari
• Ankur Moitra
• Alexander S. Wein

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

STOC Conference 2025 Conference Paper

Rounding Large Independent Sets on Expanders

• Mitali Bafna
• Jun-Ting Hsieh
• Pravesh K. Kothari

We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has its second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost 3-colorable or are promised to contain an independent set of size (1/2−є) n . Our second result above can be refined to require only a weaker vertex expansion property with an efficient certificate. In a surprising contrast to our algorithmic result, we observe that the analogous task of finding a linear-sized independent set in almost 4-colorable one-sided expanders (even when the second eigenvalue is o n (1)) is NP-hard, assuming the Unique Games Conjecture. All prior algorithms that beat the worst-case guarantees for this problem rely on bottom eigenspace enumeration techniques (following the classical spectral methods of Alon and Kahale) and require two-sided expansion, meaning a bounded number of negative eigenvalues of magnitude Ω(1). Such techniques naturally extend to almost k -colorable graphs for any constant k , in contrast to analogous guarantees on one-sided expanders, which are Unique Games-hard to achieve for k ≥ 4. Our rounding scheme builds on the method of simulating multiple samples from a pseudo-distribution introduced in Bafna et. al. for rounding Unique Games instances. The key to our analysis is a new clustering property of large independent sets in expanding graphs - every large independent set has a larger-than-expected intersection with some member of a small list - and its formalization in the low-degree sum-of-squares proof system.

FOCS Conference 2025 Conference Paper

The Quasi-Polynomial Low-Degree Conjecture is False

• Rares-Darius Buhai
• Jun-Ting Hsieh
• Aayush Jain
• Pravesh K. Kothari

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

STOC Conference 2024 Conference Paper

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

• Pravesh K. Kothari
• Peter Manohar

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

FOCS Conference 2024 Conference Paper

Efficient Certificates of Anti-Concentration Beyond Gaussians

• Ainesh Bakshi
• Pravesh K. Kothari
• Goutham Rajendran
• Madhur Tulsiani
• Aravindan Vijayaraghavan

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

FOCS Conference 2024 Conference Paper

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs

• Pravesh K. Kothari
• Peter Manohar

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

SODA Conference 2024 Conference Paper

New SDP Roundings and Certifiable Approximation for Cubic Optimization

• Jun-Ting Hsieh
• Pravesh K. Kothari
• Lucas Pesenti
• Luca Trevisan 0001

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.

STOC Conference 2024 Conference Paper

Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs

• Pravesh K. Kothari
• Aaron Potechin
• Jeff Xu

STOC Conference 2023 Conference Paper

A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity

• Aravind Gollakota
• Adam R. Klivans
• Pravesh K. Kothari

A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of testable learning , where the goal is to replace hard-to-verify distributional assumptions (such as Gaussianity) with efficiently testable ones and to require that the learner succeed whenever the unknown distribution passes the corresponding test. In this model, they gave an efficient algorithm for learning halfspaces under testable assumptions that are provably satisfied by Gaussians. In this paper we give a powerful new approach for developing algorithms for testable learning using tools from moment matching and metric distances in probability. We obtain efficient testable learners for any concept class that admits low-degree sandwiching polynomials , capturing most important examples for which we have ordinary agnostic learners. We recover the results of Rubinfeld and Vasilyan as a corollary of our techniques while achieving improved, near-optimal sample complexity bounds for a broad range of concept classes and distributions. Surprisingly, we show that the information-theoretic sample complexity of testable learning is tightly characterized by the Rademacher complexity of the concept class, one of the most well-studied measures in statistical learning theory. In particular, uniform convergence is necessary and sufficient for testable learning. This leads to a fundamental separation from (ordinary) distribution-specific agnostic learning, where uniform convergence is sufficient but not necessary.

STOC Conference 2023 Conference Paper

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

• Omar Alrabiah
• Venkatesan Guruswami
• Pravesh K. Kothari
• Peter Manohar

A code C ∶ {0,1} k → {0,1} n is a q -locally decodable code ( q -LDC) if one can recover any chosen bit b i of the message b ∈ {0,1} k with good confidence by randomly querying the encoding x = C ( b ) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp( O ( k )), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp( k o (1) ), while the best known results only show a quadratic lower bound n ≥ Ω( k 2 /log( k )) on the blocklength. In this paper, we prove a near-cubic lower bound of n ≥ Ω( k 3 /log 6 ( k )) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k . Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.

SODA Conference 2023 Conference Paper

A simple and sharper proof of the hypergraph Moore bound

• Jun-Ting Hsieh
• Pravesh K. Kothari
• Sidhanth Mohanty

STOC Conference 2023 Conference Paper

Algorithms Approaching the Threshold for Semi-random Planted Clique

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

FOCS Conference 2023 Conference Paper

Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error

• He Jia
• Pravesh K. Kothari
• Santosh S. Vempala

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

FOCS Conference 2023 Conference Paper

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

• Venkatesan Guruswami
• Jun-Ting Hsieh
• Pravesh K. Kothari
• Peter Manohar

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

STOC Conference 2023 Conference Paper

Privately Estimating a Gaussian: Efficient, Robust, and Optimal

• Daniel Alabi
• Pravesh K. Kothari
• Pranay Tankala
• Prayaag Venkat
• Fred Zhang

SODA Conference 2022 Conference Paper

Algorithmic Thresholds for Refuting Random Polynomial Systems

• Jun-Ting Hsieh
• Pravesh K. Kothari

STOC Conference 2022 Conference Paper

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

• Venkatesan Guruswami
• Pravesh K. Kothari
• Peter Manohar

We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP with only the negation patterns of the literals re-randomized with some small probability. For an n-variable smoothed instance of a k-arity CSP, our algorithm runs in n^O(ℓ) time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from 1, provided that the number of constraints is at least Õ(n) (n/ell)^(k/2 - 1). This matches, up to polylogarithmic factors in n, the trade-off between running time and the number of constraints of the state-of-the-art algorithms for refuting fully random instances of CSPs. We also make a surprising connection between the analysis of our refutation algorithm in the significantly ”randomness starved” setting of semi-random k-XOR and the existence of even covers in worst-case hypergraphs. We use this connection to positively resolve Feige’s 2008 conjecture – an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the well-known Moore bound for the girth of graphs. As a corollary, we show that polynomial-size refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the ”spectral threshold” of n^(k/2), extending the celebrated result for random 3-SAT of Feige, Kim and Ofek.

STOC Conference 2022 Conference Paper

List-decodable covariance estimation

• Misha Ivkov
• Pravesh K. Kothari

FOCS Conference 2022 Conference Paper

Polynomial-Time Power-Sum Decomposition of Polynomials

• Mitali Bafna
• Jun-Ting Hsieh
• Pravesh K. Kothari
• Jeff Xu

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

STOC Conference 2022 Conference Paper

Robustly learning mixtures of k arbitrary Gaussians

• Ainesh Bakshi
• Ilias Diakonikolas
• He Jia
• Daniel M. Kane
• Pravesh K. Kothari
• Santosh S. Vempala

SODA Conference 2021 Conference Paper

List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time

• Ainesh Bakshi
• Pravesh K. Kothari

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

STOC Conference 2021 Conference Paper

Playing unique games on certified small-set expanders

• Mitali Bafna
• Boaz Barak
• Pravesh K. Kothari
• Tselil Schramm
• David Steurer

SODA Conference 2021 Conference Paper

Strongly refuting all semi-random Boolean CSPs

• Jackson Abascal
• Venkatesan Guruswami
• Pravesh K. Kothari

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

FOCS Conference 2020 Conference Paper

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures

• Ainesh Bakshi
• Ilias Diakonikolas
• Samuel B. Hopkins 0001
• Daniel M. Kane
• Sushrut Karmalkar
• Pravesh K. Kothari

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

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

FOCS Conference 2019 Conference Paper

Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries

• Pravesh K. Kothari
• Sahil Singla 0001
• Divyarthi Mohan
• Ariel Schvartzman
• S. Matthew Weinberg

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

STOC Conference 2018 Conference Paper

Robust moment estimation and improved clustering via sum of squares

• Pravesh K. Kothari
• Jacob Steinhardt
• David Steurer

STOC Conference 2018 Conference Paper

Sum-of-squares meets nash: lower bounds for finding any equilibrium

• Pravesh K. Kothari
• Ruta Mehta

Computing Nash equilibrium (NE) in two-player game is a central question in algorithmic game theory. The main motivation of this work is to understand the power of sum-of-squares method in computing equilibria, both exact and approximate. Previous works in this context have focused on hardness of approximating “best” equilibria with respect to some natural quality measure on equilibria such as social welfare. Such results, however, do not directly relate to the complexity of the problem of finding any equilibrium. In this work, we propose a framework of roundings for the sum-of-squares algorithm (and convex relaxations in general) applicable to finding approximate/exact equilbria in two player bimatrix games. Specifically, we define the notion of oblivious roundings with verification oracle (OV). These are algorithms that can access a solution to the degree d SoS relaxation to construct a list of candidate (partial) solutions and invoke a verification oracle to check if a candidate in the list gives an (exact or approximate) equilibrium. This framework captures most known approximation algorithms in combinatorial optimization including the celebrated semi-definite programming based algorithms for Max-Cut, Constraint-Satisfaction Problems, and the recent works on SoS relaxations for Unique Games/Small-Set Expansion, Best Separable State, and many problems in unsupervised machine learning. Our main results are strong unconditional lower bounds in this framework. Specifically, we show that for є = Θ(1/ poly ( n )), there’s no algorithm that uses a o ( n )-degree SoS relaxation to construct a 2 o ( n ) -size list of candidates and obtain an є-approximate NE. For some constant є, we show a similar result for degree o (log( n )) SoS relaxation and list size n o (log( n )) . Our results can be seen as an unconditional confirmation, in our restricted algorithmic framework, of the recent Exponential Time Hypothesis for PPAD. Our proof strategy involves constructing a family of games that all share a common sum-of-squares solution but every (approximate) equilibrium of any game is far from every equilibrium of any other game in the family (in either player’s strategy). Along the way, we strengthen the classical unconditional lower bound against enumerative algorithms for finding approximate equilibria due to Daskalakis-Papadimitriou and the classical hardness of computing equilibria due to Gilbow-Zemel.

STOC Conference 2017 Conference Paper

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

• Pravesh K. Kothari
• Raghu Meka
• Prasad Raghavendra

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

STOC Conference 2017 Conference Paper

Sum of squares lower bounds for refuting any CSP

• Pravesh K. Kothari
• Ryuhei Mori
• Ryan O'Donnell
• David Witmer

Let P :{0,1} k → {0,1} be a nontrivial k -ary predicate. Consider a random instance of the constraint satisfaction problem ( P ) on n variables with Δ n constraints, each being P applied to k randomly chosen literals. Provided the constraint density satisfies Δ ≫ 1, such an instance is unsatisfiable with high probability. The refutation problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate P supports a t - wise uniform probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree d = Θ( n /Δ 2/( t -1) logΔ) (which runs in time n O ( d ) ) cannot refute a random instance of ( P ). In particular, the polynomial-time SOS algorithm requires Ω( n ( t +1)/2 ) constraints to refute random instances of CSP( P ) when P supports a t -wise uniform distribution on its satisfying assignments. Together with recent work of Lee, Raghavendra, Steurer (2015), our result also implies that any polynomial-size semidefinite programming relaxation for refutation requires at least Ω( n ( t +1)/2 ) constraints. More generally, we consider the δ-refutation problem, in which the goal is to certify that at most a (1 - δ)-fraction of constraints can be simultaneously satisfied. We show that if P is δ-close to supporting a t -wise uniform distribution on satisfying assignments, then the degree-Θ( n /Δ 2/( t - 1) logΔ) SOS algorithm cannot (δ+ 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 δ-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 (2015) and Raghavendra, Rao, Schramm (2016), this full three-way tradeoff is tight , up to lower-order factors.

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.

FOCS Conference 2016 Conference Paper

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

• Boaz Barak
• Samuel B. Hopkins 0001
• Jonathan A. Kelner
• Pravesh K. Kothari
• Ankur Moitra
• Aaron Potechin

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 analogue of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i. e. , dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.

SODA Conference 2016 Conference Paper

Communication with Contextual Uncertainty

• Badih Ghazi
• Ilan Komargodski
• Pravesh K. Kothari
• Madhu Sudan 0001

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

SODA Conference 2016 Conference Paper

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

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

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

STOC Conference 2015 Conference Paper

Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract

• Pravesh K. Kothari
• Raghu Meka

STOC Conference 2015 Conference Paper

Sum of Squares Lower Bounds from Pairwise Independence

• Boaz Barak
• Siu On Chan
• Pravesh K. Kothari

SODA Conference 2014 Conference Paper

Testing Surface Area

• Pravesh K. Kothari
• Amir Nayyeri
• Ryan O'Donnell
• Chenggang Wu 0003

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

SODA Conference 2012 Conference Paper

Submodular functions are noise stable

• Mahdi Cheraghchi
• Adam R. Klivans
• Pravesh K. Kothari
• Homin K. Lee

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