88 citations · 143 across the 20 of their papers we have counts for
37 papers
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane
The Forster transform is a method of regularizing a dataset by placing it in {\em radial isotropic position} while maintaining some of its essential properties. Forster transforms…
Graph Connectivity with Noisy Queries
Dimitris Fotakis, Evangelia Gergatsouli, Charilaos Pipis +2
Graph connectivity is a fundamental combinatorial optimization problem that arises in many practical applications, where usually a spanning subgraph of a network is used for its op…
Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning halfspaces on with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the labe…
Forster Decomposition and Learning Halfspaces with Noise
Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos
A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. While a Forster transform does not always exist, we show that any di…
A Statistical Taylor Theorem and Extrapolation of Truncated Densities
Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos +1
We show a statistical version of Taylor's theorem and apply this result to non-parametric density estimation from truncated samples, which is a classical challenge in Statistics \c…
Boosting in the Presence of Massart Noise
Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane +3
We study the problem of boosting the accuracy of a weak learner in the (distribution-independent) PAC model with Massart noise. In the Massart noise model, the label of each exampl…