49 citations · 145 across the 10 of their papers we have counts for
16 papers
Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
Kristian Georgiev, Samuel B. Hopkins
We establish a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in…
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi
We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all…
Matrix Discrepancy from Quantum Communication
Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
We develop a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of the Matrix Spence…
Smoothed Complexity of 2-player Nash Equilibria
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins +1
We prove that computing a Nash equilibrium of a two-player () game with payoffs in is PPAD-hard (under randomized reductions) even in the smoothed analysis set…
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
Samuel B. Hopkins, Jerry Li, Fred Zhang
We study the problem of estimating the mean of a distribution in high dimensions when either the samples are adversarially corrupted or the distribution is heavy-tailed. Recent dev…
Robustly Learning any Clusterable Mixture of Gaussians
Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane +1
We study the efficient learnability of high-dimensional Gaussian mixtures in the outlier-robust setting, where a small constant fraction of the data is adversarially corrupted. We…