87 citations · 305 across the 39 of their papers we have counts for
6 papers · 1 filter
Outlier-robust moment-estimation via sum-of-squares
Pravesh K. Kothari, David Steurer
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…
Better Agnostic Clustering Via Relaxed Tensor Norms
Pravesh K. Kothari, Jacob Steinhardt
We develop a new family of convex relaxations for -means clustering based on sum-of-squares norms, a relaxation of the injective tensor norm that is efficiently computable using…
The power of sum-of-squares for detecting hidden structures
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin +3
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 power…
Agnostic Learning by Refuting
Pravesh K. Kothari, Roi Livni
The sample complexity of learning a Boolean-valued function class is precisely characterized by its Rademacher complexity. This has little bearing, however, on the sample complexit…
Sum of squares lower bounds for refuting any CSP
Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell +1
Let be a nontrivial -ary predicate. Consider a random instance of the constraint satisfaction problem on variables with cons…
Quantum entanglement, sum of squares, and the log rank conjecture
Boaz Barak, Pravesh Kothari, David Steurer
For every , we give an -time algorithm for the vs \emph{Best Separable State (BSS)} problem of distinguishing, given an $n^2\times n^2…