# Robustness Verification of Polynomial Neural Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 61 references that are in the map.
- First posted on arXiv 5 Feb 2026.

## Builds on (most cited first, 27 of 27)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation](https://mlsanity.com/paper/1705.08475/) (2017)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [On the Expressive Power of Deep Polynomial Neural Networks](https://mlsanity.com/paper/1905.12207/) (2019)
- [First Three Years of the International Verification of Neural Networks Competition (VNN-COMP)](https://mlsanity.com/paper/2301.05815/) (2023)
- [Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspective](https://mlsanity.com/paper/2206.12227/) (2022)
- [Geometry of Linear Convolutional Networks](https://mlsanity.com/paper/2108.01538/) (2021)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Geometry of Polynomial Neural Networks](https://mlsanity.com/paper/2402.00949/) (2024)
- [The Euclidean distance degree of an algebraic variety](https://mlsanity.com/paper/1309.0049/) (2013)
- [Geometry of Lightning Self-Attention: Identifiability and Dimension](https://mlsanity.com/paper/2408.17221/) (2024)
- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)
- [Abstraction and Refinement: Towards Scalable and Exact Verification of Neural Networks](https://mlsanity.com/paper/2207.00759/) (2022)
- [Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approach](https://mlsanity.com/paper/2012.11761/) (2020)
- [SoundnessBench: A Soundness Benchmark for Neural Network Verifiers](https://mlsanity.com/paper/2412.03154/) (2024)
- [Constraining the outputs of ReLU neural networks](https://mlsanity.com/paper/2508.03867/) (2025)
- [Complexity of Injectivity and Verification of ReLU Neural Networks](https://mlsanity.com/paper/2405.19805/) (2024)
- [The Euclidean Distance Degree of Fermat Hypersurfaces](https://mlsanity.com/paper/1409.0684/) (2014)
- [Euclidean distance degree in manifold optimization](https://mlsanity.com/paper/2502.10336/) (2025)

## Built on by (most cited first, 3 of 3)

- [Algebraic Invariants of Lightning Self-Attention](https://mlsanity.com/paper/2604.15632/) (2026)
- [Stress-Testing Neural Network Verifiers with Provably Robust Instances](https://mlsanity.com/paper/2605.17153/) (2026)
- [Singular Learning and Occam's Razor in Deep Monomial Networks](https://mlsanity.com/paper/2606.28464/) (2026)

## Abstract (arXiv)

We study robustness verification of neural networks via metric algebraic geometry. For polynomial neural networks, certifying a robustness radius amounts to computing the distance to the algebraic decision boundary. We use the Euclidean distance (ED) degree as an intrinsic measure of the complexity of this problem, analyze the associated ED discriminant, and introduce a parameter discriminant that detects parameter values at which the ED degree drops. We derive formulas for the ED degree for several network architectures and characterize the expected number of real critical points in the infinite-width limit. We develop symbolic elimination methods to compute these quantities and homotopy-continuation methods for exact robustness certification. Finally, experiments on lightning self-attention modules reveal decision boundaries with strictly smaller ED degree than generic cubic hypersurfaces of the same ambient dimension.