142 citations · 752 across the 110 of their papers we have counts for
16 papers · 1 filter
The Sample Complexity of Robust Covariance Testing
Ilias Diakonikolas, Daniel M. Kane
We study the problem of testing the covariance matrix of a high-dimensional Gaussian in a robust setting, where the input distribution has been corrupted in Huber's contamination m…
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
Ilias Diakonikolas, Daniel M. Kane
Let be any vector space of multivariate degree- homogeneous polynomials with co-dimension at most , and be the set of points where all polynomials in {\em nearly}…
Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
Ilias Diakonikolas, Daniel M. Kane
We study the problem of PAC learning halfspaces with Massart noise. Given labeled samples from a distribution on such that the margi…
List-Decodable Mean Estimation in Nearly-PCA Time
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard +2
Traditionally, robust statistics has focused on designing estimators tolerant to a minority of contaminated data. Robust list-decodable learning focuses on the more challenging reg…
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. In the Tsybakov noise model, the label of every sample is independently flipped with…
Prisoners, Rooms, and Lightswitches
Daniel M. Kane, Scott Duke Kominers
We examine a new variant of the classic prisoners and lightswitches puzzle: A warden leads his prisoners in and out of rooms, one at a time, in some order, with each prison…