Fetching the paper…
Reading the bibliography…
We study the complexity of PAC learning halfspaces in the presence of Massart noise.
The Perceptron: a probabilistic model for information storage and organization in the brain
F. Rosenblatt · 1958
Earlier work this paper cites.
On convergence proofs on perceptrons
A. Novikoff · 1962
Earlier work this paper cites.
Perceptrons: an introduction to computational geometry
M. Minsky and S. Papert · 1968
Earlier work this paper cites.
Estimation of Dependences Based on Empirical Data: Springer Series in Statistics
V. Vapnik · 1982
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
Learning from noisy examples
D. Angluin and P. Laird · 1988
Earlier work this paper cites.
Types of noise in data for concept learning
R. H. Sloan · 1988
Earlier work this paper cites.
Decision theoretic generalizations of the PAC model for neural net and other learning applications
D. Haussler · 1992
Earlier work this paper cites.
Toward Efficient Agnostic Learning
M. Kearns, R. Schapire, and L. Sellie · 1994
Earlier work this paper cites.
A formal model of hierarchical concept learning
R. Rivest and R. Sloan · 1994
Earlier work this paper cites.
A polynomial-time algorithm for learning noisy linear threshold functions
A. Blum, A. M. Frieze, R. Kannan, and S. Vempala · 1996
Earlier work this paper cites.
Pac Learning, Noise, and Geometry
R. H. Sloan · 1996
Earlier work this paper cites.
Learning noisy perceptrons by a perceptron in polynomial time
E. Cohen · 1997
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
M. J. Kearns · 1998
Cited alongside, same era.
Complexity of lattice problems: a cryptographic perspective
D. Micciancio and S. Goldwasser · 2002
Cited alongside, same era.
Machine learning: My favorite results, directions, and open problems
A. Blum · 2003
Cited alongside, same era.
New results for learning noisy parities and halfspaces
V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami · 2006
Cited alongside, same era.
Hardness of learning halfspaces with noise
V. Guruswami and P. Raghavendra · 2006
Cited alongside, same era.
Risk bounds for statistical learning
P. Massart and E. Nedelec · 2006
Cited alongside, same era.
Complexity theoretic limitations on learning halfspaces
A. Daniely · 2016
Later among the works it cites.
On the hardness of learning with errors with binary secrets
D. Micciancio · 2018
Later among the works it cites.
On the hardness of learning with errors with binary secrets
D. Micciancio · 2018
Later among the works it cites.
Distribution-independent PAC learning of halfspaces with massart noise
I. Diakonikolas, T. Gouleakis, and C. Tzamos · 2019
Later among the works it cites.
Slide reduction, revisited - filling the gaps in SVP approximation
D. Aggarwal, J. Li, P. Q. Nguyen, and N. Stephens-Davidowitz · 2020
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Worst-case to average-case reductions based on gaussian measures
D. Micciancio and O. Regev · 2007
Cited alongside, same era.
Learning with annotation noise
E. Beigman and B. B. Klebanov · 2009
Cited alongside, same era.
Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
C. Peikert · 2009
Cited alongside, same era.
On lattices, learning with errors, random linear codes, and cryptography
O. Regev · 2009
Cited alongside, same era.
Better key sizes (and attacks) for lwe-based encryption
R. Lindner and C. Peikert · 2011
Cited alongside, same era.
Near-optimal statistical query hardness of learning halfspaces with massart noise
I. Diakonikolas and D. M. Kane · 2012
Cited alongside, same era.
S. Chen, F. Koehler, A. Moitra, and M. Yau · 2020
Later among the works it cites.
Continuous LWE
J. Bruna, O. Regev, M. J. Song, and Y. Tang · 2021
Later among the works it cites.
Boosting in the presence of massart noise
I. Diakonikolas, R. Impagliazzo, D. M. Kane, R. Lei, J. Sorrell, and C. Tzamos · 2021
Later among the works it cites.
Forster decomposition and learning halfspaces with noise
I. Diakonikolas, D. Kane, and C. Tzamos · 2021
Later among the works it cites.
Continuous lwe is as hard as lwe & applications to learning gaussian mixtures
A. Gupte, N. Vafa, and V. Vaikuntanathan · 2022
Closest in time.
Optimal SQ lower bounds for learning halfspaces with massart noise
R. Nasser and S. Tiegel · 2022
Closest in time.
Hardness of agnostically learning halfspaces from worst-case lattice problems
S. Tiegel · 2022
Closest in time.