87 citations · 305 across the 39 of their papers we have counts for
6 papers · 1 filter
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov +1
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…
Strongly refuting all semi-random Boolean CSPs
Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
We give an efficient algorithm to strongly refute \emph{semi-random} instances of all Boolean constraint satisfaction problems. The number of constraints required by our algorithm…
Playing Unique Games on Certified Small-Set Expanders
Mitali Bafna, Boaz Barak, Pravesh Kothari +2
We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint g…
Outlier-Robust Clustering of Non-Spherical Mixtures
Ainesh Bakshi, Pravesh Kothari
We give the first outlier-robust efficient algorithm for clustering a mixture of statistically separated d-dimensional Gaussians (k-GMMs). Concretely, our algorithm takes input…
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
Sumegha Garg, Pravesh K. Kothari, Ran Raz
In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming…
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 points (for some ) of which are drawn i.i.d. from a distribution with a isotropic…