# Parameterized Hardness of Zonotope Containment and Neural Network Verification

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 68 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 30 of 32)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [End to End Learning for Self-Driving Cars](https://mlsanity.com/paper/1604.07316/) (2016)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach](https://mlsanity.com/paper/1801.10578/) (2018)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [General Cutting Planes for Bound-Propagation-Based Neural Network Verification](https://mlsanity.com/paper/2208.05740/) (2022)
- [Exactly Computing the Local Lipschitz Constant of ReLU Networks](https://mlsanity.com/paper/2003.01219/) (2020)
- [Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound](https://mlsanity.com/paper/2205.00263/) (2022)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [LipBaB: Computing exact Lipschitz constant of ReLU networks](https://mlsanity.com/paper/2105.05495/) (2021)
- [The Computational Complexity of Circuit Discovery for Inner Interpretability](https://mlsanity.com/paper/2410.08025/) (2024)
- [On the Depth of Monotone ReLU Neural Networks and ICNNs](https://mlsanity.com/paper/2505.06169/) (2025)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [ℓp Row Sampling by Lewis Weights](https://mlsanity.com/paper/1412.0588/) (2014)
- [Expressivity of ReLU-Networks under Convex Relaxations](https://mlsanity.com/paper/2311.04015/) (2023)
- [The Computational Complexity of Counting Linear Regions in ReLU Neural Networks](https://mlsanity.com/paper/2505.16716/) (2025)
- [Linear Encodings for Polytope Containment Problems](https://mlsanity.com/paper/1903.05214/) (2019)
- [Reachability In Simple Neural Networks](https://mlsanity.com/paper/2203.07941/) (2022)
- [Zonotope Domains for Lagrangian Neural Network Verification](https://mlsanity.com/paper/2210.08069/) (2022)
- [Efficient Backward Reachability Using the Minkowski Difference of Constrained Zonotopes](https://mlsanity.com/paper/2207.04272/) (2022)
- [The Vector Balancing Constant for Zonotopes](https://mlsanity.com/paper/2210.16460/) (2022)

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

- [The Symmetries of Three-Layer ReLU Networks](https://mlsanity.com/paper/2605.18319/) (2026)
- [Random Parameter Noise Does Not Make Exact ReLU Verification Easy](https://mlsanity.com/paper/2607.14375/) (2026)
- [Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses](https://mlsanity.com/paper/2605.10219/) (2026)
- [Estimating Inconsistency Response Surfaces under Uncertainty in Cyber-Physical System Development](https://mlsanity.com/paper/2609.11331/) (2026)
- [Checking Leakage Witnesses versus Certifying Bounded Non-Leakage](https://mlsanity.com/paper/2609.32134/) (2026)

## Abstract (arXiv)

Neural networks with ReLU activations are a widely used model in machine learning. It is thus important to have a profound understanding of the properties of the functions computed by such networks. Recently, there has been increasing interest in the (parameterized) computational complexity of determining these properties. In this work, we close several gaps and resolve an open problem posed by Froese et al. [COLT '25] regarding the parameterized complexity of various problems related to network verification. In particular, we prove that, for all ℓ≥ 2, deciding positivity (and thus surjectivity) of a function f:ℝd→ℝ computed by an ℓ-layer ReLU network is W[ℓ-1]-hard when parameterized by the input dimension d. The case ℓ=2 implies that zonotope non-containment (a problem that is of independent interest in computational geometry, control theory, and robotics) is W[1]-hard with respect to the ambient dimension d. Moreover, we show that approximating the maximum within any multiplicative factor and computing the Lp-Lipschitz constant for p∈(0,∞] in ℓ-layer networks is NP-hard and W[ℓ-1]-hard with respect to d. For ℓ≥ 3, approximating the Lp-Lipschitz constant is NP- and W[ℓ-2]-hard. We further show that the above problems are NP- and W[t]-hard (for all t≥ 1) with respect to ℓ for constant d. Notably, our hardness results imply that the naive enumeration-based methods for these fundamental problems running in n(ℓ-1) d·operatornamepoly(N) time are all essentially optimal under the Exponential Time Hypothesis.