Samuel B. Hopkins

According to our database, Samuel B. Hopkins authored at least 34 papers between 2015 and 2023.

Collaborative distances:

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

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 D. 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

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

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

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

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

Electron. Colloquium Comput. Complex., 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

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