165 citations · 950 across the 71 of their papers we have counts for
4 papers · 1 filter
How Robust are Reconstruction Thresholds for Community Detection?
Ankur Moitra, William Perry, Alexander S. Wein
The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. In an exciting sequence of developments, motivated by de…
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…
Simple, Efficient, and Neural Algorithms for Sparse Coding
Sanjeev Arora, Rong Ge, Tengyu Ma +1
Sparse coding is a basic task in many fields including signal processing, neuroscience and machine learning where the goal is to learn a basis that enables a sparse representation…
Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Boaz Barak, Ankur Moitra
In the noisy tensor completion problem we observe entries (whose location is chosen uniformly at random) from an unknown tensor . We assume that…