165 citations · 950 across the 71 of their papers we have counts for
4 papers · 1 filter
Parallels Between Phase Transitions and Circuit Complexity?
Ankur Moitra, Elchanan Mossel, Colin Sandon
In many natural average-case problems, there are or there are believed to be critical values in the parameter space where the structure of the space of solutions changes in a funda…
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3
We prove that with high probability over the choice of a random graph from the Erdős-Rényi distribution , the -time degree Sum-of-Squares semidefinite p…
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
We show that for any odd and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…
Algorithms and Hardness for Robust Subspace Recovery
Moritz Hardt, Ankur Moitra
We consider a fundamental problem in unsupervised learning called \emph{subspace recovery}: given a collection of points in , if many but not necessarily all of t…