Samuel Hopkins

algorithms, theoretical machine learning, semidefinite programming, sum of squares optimization, convex hierarchies, bicycles.

Publications

2020+

Robustly Learning any Clusterable Mixture of Gaussians. Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar. In submission. arxiv

Subexponential LPs Approximate Max-Cut. Samuel B. Hopkins, Tselil Schramm, Luca Trevisan. In submission. arxiv

Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond. Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni. STOC 2020. arxiv

Mean Estimation with Sub-Gaussian Rates in Polynomial Time. Samuel B. Hopkins. Annals of Statistics, to appear. arxiv talk (MIFODS seminar)

2019

Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection. Yihe Dong, Samuel B. Hopkins, Jerry Li. Neurips 2019, Spotlight Presentation. arxiv code

How Hard Is Robust Mean Estimation? Samuel B. Hopkins, Jerry Li. COLT 2019. arxiv

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition. Samuel B. Hopkins, Tselil Schramm, Jonathan Shi. COLT 2019. proceedings version

Sum of Squares Meets Program Obfuscation, Revisited. Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai. Eurocrypt 2019. eprint

2018

Statistical Inference and the Sum of Squares Method. Samuel B. Hopkins. Dissertation. Recipient of Cornell CS Doctoral Dissertation Award. pdf

Mixture Models, Robustness, and Sum of Squares Proofs. Samuel B. Hopkins, Jerry Li. STOC 2018. arxiv talk 1 (BIRS) talk 2 (STOC)

2017

The power of SoS for detecting hidden structures. Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer. FOCS 2017. arxiv

Efficient Bayesian estimation from few samples: community detection and related problems. Samuel B. Hopkins, David Steurer. FOCS 2017. arxiv

2016

A nearly tight sum-of-squares lower bound for the planted clique problem. Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin. FOCS 2016, inivted to special issue. arxiv video slides (pdf)

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer. STOC 2016. arxiv slides (pptx)

On the integrality gap of degree-4 sum of squares for planted clique Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Tselil Schramm, Prasad Raghavendra. SODA 2016, invited to special issue. arxiv 1 (Hopkins-Kothari-Potechin version) and arxiv 2 (Raghavendra-Schramm version)

2015

Tensor principal component analysis via sum-of-squares proofs. Samuel B. Hopkins, Jonathan Shi, David Steurer. COLT 2015, 20 minute presentation. arxiv

2013

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret. Chicago Journal of Theoretical Computer Science. eccc