mlsanityData to 14 Oct 2026

Parameterized Hardness of Zonotope Containment and Neural Network Verification

arXiv 2509.22849 ↗First posted 26 Sep 2025cs.CC cs.DM cs.LGcited by 5

Not on the map. Why?

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.

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

32 of 68 references.

References · 32

  1. 2013Intriguing properties of neural networkscited by 5,155
  2. 2016End to End Learning for Self-Driving Carscited by 1,009
  3. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 415
  4. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  5. 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 328
  6. 2019Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networkscited by 293
  7. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  8. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 255
  9. 2018Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approachcited by 182
  10. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 161
  11. 2018Scaling provable adversarial defensescited by 143
  12. 2022General Cutting Planes for Bound-Propagation-Based Neural Network Verificationcited by 103
20 more
  1. 2020Exactly Computing the Local Lipschitz Constant of ReLU Networkscited by 102
  2. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  3. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
  4. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  5. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  6. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  7. 2021LipBaB: Computing exact Lipschitz constant of ReLU networkscited by 16
  8. 2024The Computational Complexity of Circuit Discovery for Inner Interpretabilitycited by 15
  9. 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
  10. 2024Neural Networks and (Virtual) Extended Formulationscited by 9
  11. 2014ℓp Row Sampling by Lewis Weightscited by 8
  12. 2023Expressivity of ReLU-Networks under Convex Relaxationscited by 8
  13. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  14. 2019Linear Encodings for Polytope Containment Problemscited by 6
  15. 2022Reachability In Simple Neural Networkscited by 5
  16. 2022Zonotope Domains for Lagrangian Neural Network Verificationcited by 5
  17. 2022Efficient Backward Reachability Using the Minkowski Difference of Constrained Zonotopescited by 3
  18. 2022The Vector Balancing Constant for Zonotopescited by 2
  19. 2024Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certificationcited by 2
  20. 2024Approximability of the Containment Problem for Zonotopes and Ellipsotopescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026The Symmetries of Three-Layer ReLU Networkscited by 3
  2. 2026Random Parameter Noise Does Not Make Exact ReLU Verification Easycited by 1
  3. 2026Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Lossescited by 0
  4. 2026Estimating Inconsistency Response Surfaces under Uncertainty in Cyber-Physical System Developmentcited by 0
  5. 2026Checking Leakage Witnesses versus Certifying Bounded Non-Leakagecited by 0