Samuel B. Hopkins

77 papers A* 31Journal 43Unranked 2

Year	Rank	Type	Title / 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