Fetching the paper…
Reading the bibliography…
We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on $L_p$ perturbations.
The accuracy of the Gaussian approximation to the sum of independent variates
Andrew C. Berry · 1941
Earlier work this paper cites.
On the Liapunoff limit of error in the theory of probability
Carl-Gustav Esseen · 1942
Earlier work this paper cites.
The Perceptron: a probabilistic model for information storage and organization in the brain
Frank Rosenblatt · 1958
Earlier work this paper cites.
On the factorization of the complete uniform hypergraph
Zsolt Baranyai · 1975
Earlier work this paper cites.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Nick Littlestone · 1987
Earlier work this paper cites.
Learning from noisy examples
Dana Angluin and Philip Laird · 1988
Earlier work this paper cites.
Decision theoretic generalizations of the PAC model for neural net and other learning applications
David Haussler · 1992
Earlier work this paper cites.
Toward Efficient Agnostic Learning
Michael Kearns, Robert Schapire, and Linda Sellie · 1994
Earlier work this paper cites.
Clique is hard to approximate within n 1 − ϵ n^{1-\epsilon}
Johan Håstad · 1996
Earlier work this paper cites.
The hardness of approximate optima in lattices, codes, and systems of linear equations
Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk · 1997
Earlier work this paper cites.
A decision-theoretic generalization of on-line learning and an application to boosting
Yoav Freund and Robert Schapire · 1997
Earlier work this paper cites.
A threshold of ln n for approximating set cover
Uriel Feige · 1998
Earlier work this paper cites.
A parallel repetition theorem
Ran Raz · 1998
Earlier work this paper cites.
Statistical Learning Theory
Vladimir Vapnik · 1998
Earlier work this paper cites.
Efficient learning of linear perceptrons
Shai Ben-David and Hans Ulrich Simon · 2000
Earlier work this paper cites.
A new approximate maximal margin classification algorithm
Claudio Gentile · 2001
Earlier work this paper cites.
A new approximate maximal margin classification algorithm
Claudio Gentile · 2001
Earlier work this paper cites.
General convergence results for linear discriminant updates
Adam J. Grove, Nick Littlestone, and Dale Schuurmans · 2001
Earlier work this paper cites.
Some optimal inapproximability results
Johan Håstad · 2001
Earlier work this paper cites.
On the complexity of k-SAT
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
Which problems have strongly exponential complexity?
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane · 2001
Earlier work this paper cites.
Rademacher and gaussian complexities: Risk bounds and structural results
Peter L. Bartlett and Shahar Mendelson · 2002
Cited alongside, same era.
Empirical margin distributions and bounding the generalization error of combined classifiers
Vladimir Koltchinskii and Dmitry Panchenko · 2002
Cited alongside, same era.
The robustness of the p-norm algorithms
Claudio Gentile · 2003
Cited alongside, same era.
New results for learning noisy parities and halfspaces
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami · 2006
Cited alongside, same era.
On the complexity of linear prediction: Risk bounds, margin bounds, and regularization
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari · 2008
Cited alongside, same era.
Hardness of learning halfspaces with noise
Venkatesan Guruswami and Prasad Raghavendra · 2009
From Gap-ETH to FPT-inapproximability: Clique, dominating set, and more
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan · 2017
Later among the works it cites.
A birthday repetition theorem and complexity of approximating dense CSPs
Pasin Manurangsi and Prasad Raghavendra · 2017
Later among the works it cites.
(Gap/S)ETH hardness of SVP
Divesh Aggarwal and Noah Stephens-Davidowitz · 2018
Later among the works it cites.
Parameterized intractability of even set and shortest vector problem from Gap-ETH
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi · 2018
Later among the works it cites.
Pac-learning in the presence of adversaries
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal · 2018
Later among the works it cites.
Adversarial robustness - theory and practice
Zico Colter and Aleksander Madry · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Agnostically learning halfspaces with margin errors
Shai Shalev-Shwartz, Ohad Shamir, and Karthik Sridharan · 2009
Cited alongside, same era.
Two-query PCP with subconstant error
Dana Moshkovitz and Ran Raz · 2010
Cited alongside, same era.
Learning kernel-based halfspaces with the zero-one loss
Shai Shalev-Shwartz, Ohad Shamir, and Karthik Sridharan · 2010
Cited alongside, same era.
Lower bounds based on the exponential time hypothesis
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh · 2011
Cited alongside, same era.
Learning large-margin halfspaces with more malicious noise
Phil Long and Rocco Servedio · 2011
Cited alongside, same era.
Learning halfspaces with the zero-one loss: Time-accuracy tradeoffs
Aharon Birnbaum and Shai Shalev-Shwartz · 2012
Cited alongside, same era.
Later among the works it cites.
ETH-hardness of approximating 2-CSPs and directed steiner network
Irit Dinur and Pasin Manurangsi · 2018
Later among the works it cites.
Adversarially robust generalization requires more data
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry · 2018
Later among the works it cites.
On robustness to adversarial examples and polynomial optimization
Pranjal Awasthi, Abhratanu Dutta, and Aravindan Vijayaraghavan · 2019
Later among the works it cites.
Parameterized intractability of even set and shortest vector problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, and Dániel Marx · 2019
Later among the works it cites.
Adversarial examples from computational constraints
Sebastien Bubeck, Yin-Tat Lee, Eric Price, and Ilya P. Razenshteyn · 2019
Later among the works it cites.
Tight FPT approximations for k-median and k-means
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li · 2019
Later among the works it cites.
The constant inapproximability of the parameterized dominating set problem
Yijia Chen and Bingkai Lin · 2019
Later among the works it cites.
Nearly tight bounds for robust proper learning of halfspaces with a margin
Ilias Diakonikolas, Daniel Kane, and Pasin Manurangsi · 2019
Later among the works it cites.
Computational limitations in robust classification and win-win results
Akshay Degwekar, Preetum Nakkiran, and Vinod Vaikuntanathan · 2019
Later among the works it cites.
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Vishesh Jain, Frederic Koehler, and Andrej Risteski · 2019
Later among the works it cites.
On the parameterized complexity of approximating dominating set
Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi · 2019
Later among the works it cites.
A simple gap-producing reduction for the parameterized set cover problem
Bingkai Lin · 2019
Later among the works it cites.
VC classes are adversarially robustly learnable, but only improperly
Omar Montasser, Steve Hanneke, and Nathan Srebro · 2019
Later among the works it cites.
Tight running time lower bounds for strong inapproximability of maximum k -coverage, unique set cover and related problems (via t -wise agreement testing theorem)
Pasin Manurangsi · 2020
Closest in time.
Efficiently learning adversarially robust halfspaces with noise
Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nathan Srebro · 2020
Closest in time.