165 citations · 950 across the 71 of their papers we have counts for
6 papers · 1 filter
Message-passing algorithms for synchronization problems over compact groups
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira +1
Various alignment problems arising in cryo-electron microscopy, community detection, time synchronization, computer vision, and other fields fall into a common framework of synchro…
Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models
Ankur Moitra
In this paper we introduce a new approach for approximately counting in bounded degree systems with higher-order constraints. Our main result is an algorithm to approximately count…
Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira +1
A central problem of random matrix theory is to understand the eigenvalues of spiked random matrix models, in which a prominent eigenvector is planted into a random matrix. These d…
Provable Algorithms for Inference in Topic Models
Sanjeev Arora, Rong Ge, Frederic Koehler +2
Recently, there has been considerable progress on designing algorithms with provable guarantees -- typically using linear algebraic methods -- for parameter learning in latent vari…
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…
Robust Estimators in High Dimensions without the Computational Intractability
Ilias Diakonikolas, Gautam Kamath, Daniel Kane +3
We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an -fraction of the samples. Such questions…