
Statistical Query Algorithms and LowDegree Tests Are Almost Equivalent
Researchers currently use a number of approaches to predict and substant...
read it

Estimating RankOne Spikes from HeavyTailed Noise via SelfAvoiding Walks
We study symmetric spiked matrix models with respect to a general class ...
read it

Robust and HeavyTailed Mean Estimation Made Simple, via Regret Minimization
We study the problem of estimating the mean of a distribution in high di...
read it

Smoothed Complexity of 2player Nash Equilibria
We prove that computing a Nash equilibrium of a twoplayer (n × n) game ...
read it

Robustly Learning any Clusterable Mixture of Gaussians
We study the efficient learnability of highdimensional Gaussian mixture...
read it

Algorithms for HeavyTailed Statistics: Regression, Covariance Estimation, and Beyond
We study efficient algorithms for linear regression and covariance estim...
read it

Subexponential LPs Approximate MaxCut
We show that for every ε > 0, the degreen^ε SheraliAdams linear progra...
read it

Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
We study two problems in highdimensional robust statistics: robust mean...
read it

How Hard Is Robust Mean Estimation?
Robust mean estimation is the problem of estimating the mean μ∈R^d of a ...
read it

Mean Estimation with SubGaussian Rates in Polynomial Time
We study polynomial time algorithms for estimating the mean of a heavyt...
read it

SubGaussian Mean Estimation in Polynomial Time
We study polynomial time algorithms for estimating the mean of a random ...
read it

Mixture Models, Robustness, and Sum of Squares Proofs
We use the Sum of Squares method to develop new efficient algorithms for...
read it

The power of sumofsquares for detecting hidden structures
We study planted problemsfinding hidden structures in random noisy in...
read it

Bayesian estimation from few samples: community detection and related problems
We propose an efficient metaalgorithm for Bayesian estimation problems ...
read it

Fast spectral algorithms from sumofsquares proofs: tensor decomposition and planted sparse vectors
We consider two problems that arise in machine learning applications: th...
read it
Samuel B. Hopkins
is this you? claim profile