Fetching the paper…
Reading the bibliography…
We continue the study of statistical/computational tradeoffs in learning robust classifiers, following the recent work of Bubeck, Lee, Price and Razenshteyn who showed examples of classification tasks where (a) an efficient robust classifier exists, in the small-perturbation regime; (b) a non-robust classifier can be learned efficiently; but (c) it is computationally hard to learn a robust classifier, assuming the hardness of factoring large numbers.
A Simple Unpredictable Pseudo-Random Number Generator
Lenore Blum, Manuel Blum, and Mike Shub · 1986
Earlier work this paper cites.
How to Construct Random Functions
Oded Goldreich, Shafi Goldwasser, and Silvio Micali · 1986
Earlier work this paper cites.
The Hardness of Decoding Linear Codes with Preprocessing
Jehoshua Bruck and Moni Naor · 1990
Earlier work this paper cites.
Efficient, Perfect Polynomial Random Number Generators
Silvio Micali and Claus-Peter Schnorr · 1991
Earlier work this paper cites.
On the Learnability of Discrete Distributions
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E Schapire, and Linda Sellie · 1994
Earlier work this paper cites.
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata
Michael Kearns and Leslie Valiant · 1994
Earlier work this paper cites.
Hard-core distributions for somewhat hard problems
Russell Impagliazzo · 1995
Earlier work this paper cites.
Adaptive game playing using multiplicative weights
Yoav Freund, Robert E Schapire, et al · 1999
Earlier work this paper cites.
Expander-based Constructions of Efficiently Decodable Codes
Venkatesan Guruswami and Piotr Indyk · 2001
Earlier work this paper cites.
Foundations of Cryptography: Basic Tools, 2001
Oded Goldreich · 2001
Earlier work this paper cites.
The hardness of the closest vector problem with preprocessing
Daniele Micciancio · 2001
Earlier work this paper cites.
More on Average Case vs Approximation Complexity
Michael Alekhnovich · 2003
Earlier work this paper cites.
Noise-tolerant Learning, the Parity Problem, and the Statistical Query Model
Avrim Blum, Adam Kalai, and Hal Wasserman · 2003
Earlier work this paper cites.
Adversarial classification
Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, Deepak Verma, et al · 2004
Cited alongside, same era.
Improved Inapproximability of Lattice and Coding Problems With Preprocessing
Oded Regev · 2004
Cited alongside, same era.
Adversarial learning
Daniel Lowd and Christopher Meek · 2005
Cited alongside, same era.
The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem
Vadim Lyubashevsky · 2005
Cited alongside, same era.
Learning to impersonate
Moni Naor and Guy N Rothblum · 2006
Cited alongside, same era.
Trapdoors for Hard Lattices and New Cryptographic Constructions
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan · 2008
Cited alongside, same era.
Towards evaluating the robustness of neural networks
Nicholas Carlini and David Wagner · 2017
Later among the works it cites.
Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples
Anish Athalye, Nicholas Carlini, and David Wagner · 2018
Later among the works it cites.
Adversarial examples from cryptographic pseudo-random generators
Sébastien Bubeck, Yin Tat Lee, Eric Price, and Ilya P. Razenshteyn · 2018
Later among the works it cites.
Adversarial examples from computational constraints
Sébastien Bubeck, Eric Price, and Ilya Razenshteyn · 2018
Later among the works it cites.
Wild patterns: Ten years after the rise of adversarial machine learning
Battista Biggio and Fabio Roli · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
New algorithms for learning in presence of errors
Sanjeev Arora and Rong Ge · 2011
Cited alongside, same era.
Commitments and efficient zero-knowledge proofs from learning parity with noise
Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, and Aris Tentes · 2012
Cited alongside, same era.
A few more notes on NSA random number generators, 2013
Matthew Green · 2013
Cited alongside, same era.
Intriguing properties of neural networks
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus · 2013
Cited alongside, same era.
A uniform min-max theorem with applications in cryptography
Salil Vadhan and Colin Jia Zheng · 2013
Cited alongside, same era.
Explaining and harnessing adversarial examples. corr (2015)
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy · 2015
Cited alongside, same era.
Adversarial vulnerability for any classifier
Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi · 2018
Later among the works it cites.
Adversarial spheres, 2018
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian Goodfellow · 2018
Later among the works it cites.
Can adversarially robust learning leverage computational hardness?
Saeed Mahloujifar and Mohammad Mahmoody · 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.
Statistical Difference Beyond the Polarizing Regime
Itay Berman, Akshay Degwekar, Ron D. Rothblum, and Prashant Nalini Vasudevan · 2019
Closest in time.
Computational Limitations in Robust Classification and Win-Win Results
Akshay Degwekar and Vinod Vaikuntanathan · 2019
Closest in time.
Personal communication, 2019
Nadia Heninger · 2019
Closest in time.
Adversarial robustness may be at odds with simplicity
Preetum Nakkiran · 2019
Closest in time.