49 citations · 234 across the 21 of their papers we have counts for
4 papers · 1 filter
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Matthew Brennan, Guy Bresler, Samuel B. Hopkins +2
Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach…
How Hard Is Robust Mean Estimation?
Samuel B. Hopkins, Jerry Li
Robust mean estimation is the problem of estimating the mean of a -dimensional distribution from a list of independent samples, an -fraction of which…
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…
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin
The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size added to an \Erdos-\Renyi graph $G \si…