Sam Hopkins

According to our database, Sam Hopkins authored at least 48 papers between 2013 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Rescaled Influence Functions: Accurate Data Attribution in High Dimension.

Ittai Rubinstein, Samuel B. Hopkins

CoRR, June, 2025

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More.

Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications.

Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Robustness Auditing for Linear Regression: To Singularity and Beyond.

Ittai Rubinstein, Samuel B. Hopkins

Proceedings of the Thirteenth International Conference on Learning Representations, 2025

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams.

Ainesh Bakshi, Vincent Cohen-Addad, Rajesh Jayaram, Sam Hopkins, Silvio Lattanzi

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

2024

Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares.

Gavin Brown, Jonathan Hayase, Samuel B. Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C. Perdomo, Adam Smith

CoRR, 2024

Adversarially-Robust Inference on Trees via Belief Propagation.

Samuel B. Hopkins, Anqi Li

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation.

Shivam Gupta, Samuel B. Hopkins, Eric C. Price

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract.

Gavin Brown, Jonathan Hayase, Samuel B. Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C. Perdomo, Adam Smith

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies.

Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi

CoRR, 2023

Towards Practical Robustness Auditing for Linear Regression.

Daniel Freund, Samuel B. Hopkins

CoRR, 2023

Robustness Implies Privacy in Statistical Estimation.

Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

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

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions.

Gavin Brown, Samuel B. Hopkins, Adam Smith

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Matrix discrepancy from Quantum communication.

Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism.

Samuel B. Hopkins, Gautam Kamath, Mahbod Majid

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation.

Kristian Georgiev, Samuel B. Hopkins

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

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

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

Counterexamples to New Circular Security Assumptions Underlying iO.

Samuel B. Hopkins, Aayush Jain, Huijia Lin

IACR Cryptol. ePrint Arch., 2021

Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent.

Matthew S. Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, Tselil Schramm

Proceedings of the Conference on Learning Theory, 2021

2020

Robustly Learning any Clusterable Mixture of Gaussians.

Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar

CoRR, 2020

Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond.

Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization.

Samuel B. Hopkins, Jerry Li, Fred Zhang

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks.

Jingqiu Ding, Samuel B. Hopkins, David Steurer

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Subexponential LPs Approximate Max-Cut.

Samuel B. Hopkins, Tselil Schramm, Luca Trevisan

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Smoothed Complexity of 2-player Nash Equilibria.

Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures.

Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.

Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin

SIAM J. Comput., 2019

Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection.

Yihe Dong, Samuel B. Hopkins, Jerry Li

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi

Proceedings of the Conference on Learning Theory, 2019

How Hard is Robust Mean Estimation?

Samuel B. Hopkins, Jerry Li

Proceedings of the Conference on Learning Theory, 2019

2018

Statistical Inference and the Sum of Squares Method.

Samuel B. Hopkins

PhD thesis, 2018

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique.

Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm

ACM Trans. Algorithms, 2018

Sum-of-Squares Meets Program Obfuscation, Revisited.

Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai

IACR Cryptol. ePrint Arch., 2018

Sub-Gaussian Mean Estimation in Polynomial Time.

Samuel B. Hopkins

CoRR, 2018

Mixture models, robustness, and sum of squares proofs.

Samuel B. Hopkins, Jerry Li

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Bayesian estimation from few samples: community detection and related problems.

Samuel B. Hopkins, David Steurer

CoRR, 2017

Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems.

Samuel B. Hopkins, David Steurer

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

The Power of Sum-of-Squares for Detecting Hidden Structures.

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Pattern Avoidance in Poset Permutations.

Sam Hopkins, Morgan Weiler

Order, 2016

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Interlacing networks: Birational RSK, the octahedron recurrence, and Schur function identities.

Miriam Farber, Sam Hopkins, Wuttisak Trongsiriwat

J. Comb. Theory A, 2015

Speeding up sum-of-squares for tensor decomposition and planted sparse vectors.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

CoRR, 2015

Tensor principal component analysis via sum-of-squares proofs.

Samuel B. Hopkins, Jonathan Shi, David Steurer

CoRR, 2015

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

CoRR, 2015

Tensor principal component analysis via sum-of-square proofs.

Samuel B. Hopkins, Jonathan Shi, David Steurer

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Another proof of Wilmes' conjecture.

Sam Hopkins

Discret. Math., 2014

2013

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.

Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret

Chic. J. Theor. Comput. Sci., 2013