49 citations · 234 across the 21 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.DS2017★ 5 cited
Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins, Jerry Li
We use the Sum of Squares method to develop new efficient algorithms for learning well-separated mixtures of Gaussians and robust mean estimation, both in high dimensions, that sub…
cs.DS2017
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…
cs.DS2017★ 16 cited
Bayesian estimation from few samples: community detection and related problems
Samuel B. Hopkins, David Steurer
We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm i…