
SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation
We develop a general framework to significantly reduce the degree of sum...
read it

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
We study efficient algorithms for Sparse PCA in standard statistical mod...
read it

Regress Consistently when Oblivious Outliers Overwhelm
We give a novel analysis of the Huber loss estimator for consistent robu...
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

Playing Unique Games on Certified SmallSet Expanders
We give an algorithm for solving unique games (UG) instances whose const...
read it

Highdimensional estimation via sumofsquares proofs
Estimation is the computational task of recovering a hidden parameter x ...
read it

SmallSet Expansion in Shortcode Graph and the 2to2 Conjecture
Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (...
read it

Outlierrobust momentestimation via sumofsquares
We develop efficient algorithms for estimating lowdegree moments of unk...
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 and robust tensor decomposition with applications to dictionary learning
We develop fast spectral algorithms for tensor decomposition that match ...
read it

Exact tensor completion with sumofsquares
We obtain the first polynomialtime algorithm for exact tensor completio...
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

Dictionary Learning and Tensor Decomposition via the SumofSquares Method
We give a new approach to the dictionary learning (also known as "sparse...
read it
David Steurer
is this you? claim profile