Samuel B. Hopkins

77 papers A* 31Journal 43Unranked 2
YearRankTypeTitle / Venue / Authors
2026 A* conf
Additive Approximation Schemes for Low-Dimensional Embeddings.
SODA
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
2026 J jnl
SNARGs for NP and Non-Signaling PCPs, Revisited.
IACR Cryptol. ePrint Arch.
Lalita Devadas, Samuel B. Hopkins, Yael Tauman Kalai, Pravesh K. Kothari, Alex Lombardi, Surya Mathialagan
2025 J jnl
Additive Approximation Schemes for Low-Dimensional Embeddings.
CoRR
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
2025 J jnl
On the Accuracy of Newton Step and Influence Function Data Attributions.
CoRR
Ittai Rubinstein, Samuel B. Hopkins
2025 J jnl
Rescaled Influence Functions: Accurate Data Attribution in High Dimension.
CoRR
Ittai Rubinstein, Samuel B. Hopkins
2025 A* conf
Robustness Auditing for Linear Regression: To Singularity and Beyond.
ICLR
Ittai Rubinstein, Samuel B. Hopkins
2025 A* conf
SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications.
STOC
Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel
2025 A* conf
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More.
STOC
Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel
2024 A* conf
Adversarially-Robust Inference on Trees via Belief Propagation.
COLT
Samuel B. Hopkins, Anqi Li
2024 J jnl
Adversarially-Robust Inference on Trees via Belief Propagation.
CoRR
Samuel B. Hopkins, Anqi Li
2024 A* conf
Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation.
COLT
Shivam Gupta, Samuel B. Hopkins, Eric C. Price
2024 A* conf
Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract.
COLT
Gavin Brown, Jonathan Hayase, Samuel B. Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C. Perdomo, Adam Smith
2024 J jnl
Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares.
CoRR
Gavin Brown, Jonathan Hayase, Samuel B. Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C. Perdomo, Adam Smith
2024 J jnl
Robustness Auditing for Linear Regression: To Singularity and Beyond.
CoRR
Ittai Rubinstein, Samuel B. Hopkins
2024 J jnl
SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications.
CoRR
Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel
2024 J jnl
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More.
CoRR
Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel
2023 J jnl
A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies.
CoRR
Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi
2023 A* conf
Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions.
COLT
Gavin Brown, Samuel B. Hopkins, Adam Smith
2023 J jnl
Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions.
CoRR
Gavin Brown, Samuel B. Hopkins, Adam D. Smith
2023 A* conf
Robustness Implies Privacy in Statistical Estimation.
STOC
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan
2023 A* conf
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination.
FOCS
Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan
2023 J jnl
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination.
CoRR
Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan
2023 J jnl
Towards Practical Robustness Auditing for Linear Regression.
CoRR
Daniel Freund, Samuel B. Hopkins
2022 J jnl
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition.
CoRR
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi
2022 A* conf
Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism.
STOC
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid
2022 A* conf
Matrix discrepancy from Quantum communication.
STOC
Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
2022 A* conf
Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation.
NeurIPS
Kristian Georgiev, Samuel B. Hopkins
2022 J jnl
Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation.
CoRR
Kristian Georgiev, Samuel B. Hopkins
2022 J jnl
Robustness Implies Privacy in Statistical Estimation.
CoRR
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan
2022 A* conf
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics.
NeurIPS
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik
2022 J jnl
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics.
CoRR
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik
2021 — conf
Counterexamples to New Circular Security Assumptions Underlying iO.
CRYPTO (2)
Samuel B. Hopkins, Aayush Jain, Huijia Lin
2021 J jnl
Counterexamples to New Circular Security Assumptions Underlying iO.
IACR Cryptol. ePrint Arch.
Samuel B. Hopkins, Aayush Jain, Huijia Lin
2021 J jnl
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism.
CoRR
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid
2021 J jnl
Matrix Discrepancy from Quantum Communication.
CoRR
Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
2021 A* conf
Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent.
COLT
Matthew S. Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, Tselil Schramm
2020 A* conf
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond.
STOC
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni
2020 A* conf
Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks.
NeurIPS
Jingqiu Ding, Samuel B. Hopkins, David Steurer
2020 J jnl
Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks.
CoRR
Jingqiu Ding, Samuel B. Hopkins, David Steurer
2020 A* conf
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures.
FOCS
Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari
2020 A* conf
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization.
NeurIPS
Samuel B. Hopkins, Jerry Li, Fred Zhang
2020 J jnl
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization.
CoRR
Samuel B. Hopkins, Jerry Li, Fred Zhang
2020 J jnl
Robustly Learning any Clusterable Mixture of Gaussians.
CoRR
Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar
2020 A* conf
Smoothed Complexity of 2-player Nash Equilibria.
FOCS
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
2020 J jnl
Smoothed Complexity of 2-player Nash Equilibria.
CoRR
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
2020 J jnl
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent.
CoRR
Matthew S. Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, Tselil Schramm
2020 A* conf
Subexponential LPs Approximate Max-Cut.
FOCS
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
2019 J jnl
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.
SIAM J. Comput.
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin
2019 A* conf
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition.
COLT
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi
2019 J jnl
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond.
CoRR
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni
2019 J jnl
How Hard Is Robust Mean Estimation?
CoRR
Samuel B. Hopkins, Jerry Li
2019 A* conf
How Hard is Robust Mean Estimation?
COLT
Samuel B. Hopkins, Jerry Li
2019 A* conf
Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection.
NeurIPS
Yihe Dong, Samuel B. Hopkins, Jerry Li
2019 J jnl
Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection.
CoRR
Yihe Dong, Samuel B. Hopkins, Jerry Li
2019 J jnl
Subexponential LPs Approximate Max-Cut.
CoRR
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
2019 — conf
Sum-of-Squares Meets Program Obfuscation, Revisited.
EUROCRYPT (1)
Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai
2018 A* conf
Mixture models, robustness, and sum of squares proofs.
STOC
Samuel B. Hopkins, Jerry Li
2018 J jnl
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique.
ACM Trans. Algorithms
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
2018 — —
Statistical Inference and the Sum of Squares Method.
Samuel B. Hopkins
2018 J jnl
Sub-Gaussian Mean Estimation in Polynomial Time.
CoRR
Samuel B. Hopkins
2018 J jnl
Sum-of-Squares Meets Program Obfuscation, Revisited.
IACR Cryptol. ePrint Arch.
Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai
2017 J jnl
Bayesian estimation from few samples: community detection and related problems.
CoRR
Samuel B. Hopkins, David Steurer
2017 A* conf
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems.
FOCS
Samuel B. Hopkins, David Steurer
2017 J jnl
Mixture Models, Robustness, and Sum of Squares Proofs.
CoRR
Samuel B. Hopkins, Jerry Li
2017 A* conf
The Power of Sum-of-Squares for Detecting Hidden Structures.
FOCS
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2017 J jnl
The power of sum-of-squares for detecting hidden structures.
CoRR
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2016 A* conf
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.
FOCS
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
2016 J jnl
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.
CoRR
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
2016 J jnl
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.
Electron. Colloquium Comput. Complex.
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
2016 A* conf
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors.
STOC
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer
2016 A* conf
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique.
SODA
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
2015 J jnl
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four.
CoRR
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin
2015 J jnl
Speeding up sum-of-squares for tensor decomposition and planted sparse vectors.
CoRR
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer
2015 A* conf
Tensor principal component analysis via sum-of-square proofs.
COLT
Samuel B. Hopkins, Jonathan Shi, David Steurer
2015 J jnl
Tensor principal component analysis via sum-of-squares proofs.
CoRR
Samuel B. Hopkins, Jonathan Shi, David Steurer
2013 J jnl
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.
Chic. J. Theor. Comput. Sci.
Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret
2012 J jnl
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.
Electron. Colloquium Comput. Complex.
Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret