# A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance

arXiv: https://arxiv.org/abs/1901.10861 · HTML: https://mlsanity.com/paper/1901.10861/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2019.

## Built on by (most cited first, 30 of 32)

- [Amplitude-Phase Recombination: Rethinking Robustness of Convolutional Neural Networks in Frequency Domain](https://mlsanity.com/paper/2108.08487/) (2021)
- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [The 2021 Image Similarity Dataset and Challenge](https://mlsanity.com/paper/2106.09672/) (2021)
- [Gradient Methods Provably Converge to Non-Robust Networks](https://mlsanity.com/paper/2202.04347/) (2022)
- [A single gradient step finds adversarial examples on random two-layers neural networks](https://mlsanity.com/paper/2104.03863/) (2021)
- [Adversarial Examples in Multi-Layer Random ReLU Networks](https://mlsanity.com/paper/2106.12611/) (2021)
- [The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks](https://mlsanity.com/paper/2303.01456/) (2023)
- [Shift Invariance Can Reduce Adversarial Robustness](https://mlsanity.com/paper/2103.02695/) (2021)
- [Dompteur: Taming Audio Adversarial Examples](https://mlsanity.com/paper/2102.05431/) (2021)
- [Thief, Beware of What Get You There: Towards Understanding Model Extraction Attack](https://mlsanity.com/paper/2104.05921/) (2021)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Adversarial Examples Exist in Two-Layer ReLU Networks for Low Dimensional Linear Subspaces](https://mlsanity.com/paper/2303.00783/) (2023)
- [Who's Afraid of Adversarial Transferability?](https://mlsanity.com/paper/2105.00433/) (2021)
- [Adversarial Robustness is at Odds with Lazy Training](https://mlsanity.com/paper/2207.00411/) (2022)
- [Robust Classification Under ℓ0 Attack for the Gaussian Mixture Model](https://mlsanity.com/paper/2104.02189/) (2021)
- [Fairness Increases Adversarial Vulnerability](https://mlsanity.com/paper/2211.11835/) (2022)
- [Hamming Similarity and Graph Laplacians for Class Partitioning and Adversarial Image Detection](https://mlsanity.com/paper/2305.01808/) (2023)
- [Dual Graphs of Polyhedral Decompositions for the Detection of Adversarial Attacks](https://mlsanity.com/paper/2211.13305/) (2022)
- [Upper and lower bounds for the Lipschitz constant of random neural networks](https://mlsanity.com/paper/2311.01356/) (2023)
- [Understanding Robustness in Teacher-Student Setting: A New Perspective](https://mlsanity.com/paper/2102.13170/) (2021)
- [Towards Explaining Adversarial Examples Phenomenon in Artificial Neural Networks](https://mlsanity.com/paper/2107.10599/) (2021)
- [Efficient and Robust Classification for Sparse Attacks](https://mlsanity.com/paper/2201.09369/) (2022)
- [MALT Powers Up Adversarial Attacks](https://mlsanity.com/paper/2407.02240/) (2024)
- [A Provable Energy-Guided Test-Time Defense Boosting Adversarial Robustness of Large Vision-Language Models](https://mlsanity.com/paper/2603.26984/) (2026)
- [Binary Classification Under ℓ0 Attacks for General Noise Distribution](https://mlsanity.com/paper/2203.04855/) (2022)
- [Beyond Empirical Risk Minimization: Local Structure Preserving Regularization for Improving Adversarial Robustness](https://mlsanity.com/paper/2303.16861/) (2023)
- [A Theoretical Perspective on Subnetwork Contributions to Adversarial Robustness](https://mlsanity.com/paper/2307.03803/) (2023)
- [On the Computational Entanglement of Distant Features in Adversarial Machine Learning](https://mlsanity.com/paper/2309.15669/) (2023)
- [Generalization Properties of Adversarial Training for ℓ0-Bounded Adversarial Attacks](https://mlsanity.com/paper/2402.03576/) (2024)
- [Human-Imperceptible Physical Adversarial Attack for NIR Face Recognition Models](https://mlsanity.com/paper/2504.15823/) (2025)

## Abstract (arXiv)

The existence of adversarial examples in which an imperceptible change in the input can fool well trained neural networks was experimentally discovered by Szegedy et al in 2013, who called them "Intriguing properties of neural networks". Since then, this topic had become one of the hottest research areas within machine learning, but the ease with which we can switch between any two decisions in targeted attacks is still far from being understood, and in particular it is not clear which parameters determine the number of input coordinates we have to change in order to mislead the network. In this paper we develop a simple mathematical framework which enables us to think about this baffling phenomenon from a fresh perspective, turning it into a natural consequence of the geometry of ℝn with the L0 (Hamming) metric, which can be quantitatively analyzed. In particular, we explain why we should expect to find targeted adversarial examples with Hamming distance of roughly m in arbitrarily deep neural networks which are designed to distinguish between m input classes.