Adversarially-Robust Inference on Trees via Belief Propagation. Samuel B. Hopkins, Anqi Li. Manuscript. [arxiv]https://arxiv.org/abs/2404.00768
A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies. Ainesh Bakshi, Vincent Cohen-Addad, Rajesh Jayram, Samuel B. Hopkins, Silvio Lattanzi. Manuscript. arxiv
Towards Practical Robustness Auditing for Linear Regression. Daniel Freund, Samuel B. Hopkins. Manuscript. arxiv
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan. FOCS 2023. arxiv
Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions. Gavin Brown, Samuel B. Hopkins, Adam Smith. COLT 2023. Best student paper award, shared with this paper. arxiv blog post
Robustness Implies Privacy in Statistical Estimation. Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan. STOC 2023. arxiv. Oral presentation at TPDP 2023.
Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation. Kristian Georgiev, Samuel B. Hopkins. NeurIPS 2022. arxiv
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics. Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik. NeurIPS 2022, Oral. arxiv
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism. Samuel B. Hopkins, Gautam Kamath, Mahbod Majid. STOC 2022. arxiv
Matrix Discrepancy from Quantum Communication. Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty. STOC 2022. Invited to special issue. arxiv
Counterexamples to New Circular Security Assumptions Underlying iO. Samuel B. Hopkins, Aayush Jain, Rachel Lin. Crypto 2021. eprint slides talk
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent. Matthew Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, Tselil Schramm. COLT 2021. Best paper runner-up. arxiv
Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks. Jingqiu Ding, Samuel B. Hopkins, David Steurer. NeurIPS 2020, Spotlight. arxiv
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization. Samuel B. Hopkins, Jerry Li, Fred Zhang. NeurIPS 2020. arxiv
Smoothed Complexity of 2-Player Nash Equilibria. Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein. FOCS 2020. arxiv
Robustly Learning any Clusterable Mixture of Gaussians. Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar. FOCS 2020. arxiv (Conference version to be merged with this paper.) talk (Simons seminar)
Subexponential LPs Approximate Max-Cut. Samuel B. Hopkins, Tselil Schramm, Luca Trevisan. FOCS 2020. 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 talk (Simons workshop)
Mean Estimation with Sub-Gaussian Rates in Polynomial Time. Samuel B. Hopkins. Annals of Statistics, 2020. arxiv talk (MIFODS seminar)
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
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)
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
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, invited 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)
Tensor principal component analysis via sum-of-squares proofs. Samuel B. Hopkins, Jonathan Shi, David Steurer. COLT 2015, 20 minute presentation. arxiv
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