Get Started
Home
Topics
Search
Library
Research questionHow do input dimension and network depth affect the tractability of verifying properties of ReLU networks?ReLU-network analysis involves deciding properties such as positivity or surjectivity, approximating maxima, and computing Lipschitz constants. The computational difficulty of these tasks can change substantially with the network's input dimension and depth.
AI
Machine Learning
Neural and Evolutionary Computing
Research Paper
Technology
Latest papersRecent research connected to this question, newest first.Parameterized Hardness of Zonotope Containment and Neural Network VerificationThe results cover ℓ-layer ReLU networks and, for two-layer networks, zonotope non-containment. They establish W-hardness and NP-hardness results parameterized by input dimension or depth, including hardness for positivity, maximum approximation, and Lp-Lipschitz constants; they also show that naive enumeration is essentially optimal under the Exponential Time Hypothesis.research paper · Sep 3, 2026
Related questions
How can we characterize when deep ReLU networks with different architectures or parameters compute the same function on the unit cube?How do initialization correlation decay and feature-function Hermite rank determine residual networks’ scaling and continuous-depth limit?How can residual networks approximate high-dimensional semilinear heat-equation solutions without exponential parameter growth?How does the leaky-ReLU parameter alter critical-point bifurcations and symmetry-breaking stability in shallow networks?