Cover Image

Complexity of Injectivity and Verification of ReLU Neural Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Froese, Vincent, Grillo, Moritz, Skutella, Martin
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Discrete Mathematics Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parameterized Hardness of Zonotope Containment and Neural Network Verification
by: Froese, Vincent, et al.
Published: (2025)

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
by: Stargalla, Moritz, et al.
Published: (2025)

Topological Expressivity of ReLU Neural Networks
by: Ergen, Ekin, et al.
Published: (2023)

Towards Lower Bounds on the Depth of ReLU Neural Networks
by: Hertrich, Christoph, et al.
Published: (2021)

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
by: Hertrich, Christoph, et al.
Published: (2020)

The Symmetries of Three-Layer ReLU Networks
by: Gegenfurtner, Johanna Marie, et al.
Published: (2026)

On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth
by: Averkov, Gennadiy, et al.
Published: (2025)

On the Depth of Monotone ReLU Neural Networks and ICNNs
by: Bakaev, Egor, et al.
Published: (2025)

ReLU Networks for Exact Generation of Similar Graphs
by: Ghafoor, Mamoona, et al.
Published: (2026)

Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance
by: Ghafoor, Mamoona, et al.
Published: (2025)

Mistake-bounded online learning with operation caps
by: Geneson, Jesse, et al.
Published: (2025)

Neural Networks and (Virtual) Extended Formulations
by: Hertrich, Christoph, et al.
Published: (2024)

Arithmetic Circuits and Neural Networks for Regular Matroids
by: Hertrich, Christoph, et al.
Published: (2025)

Nearest Neighbor Representations of Neural Circuits
by: Kilic, Kordag Mehmet, et al.
Published: (2024)

On the Expressibility of the Reconstructional Color Refinement
by: Arvind, V., et al.
Published: (2024)

The Parameterized Complexity of Computing the VC-Dimension
by: Foucaud, Florent, et al.
Published: (2025)

The Computational Complexity of Positive Non-Clashing Teaching in Graphs
by: Ganian, Robert, et al.
Published: (2025)

Computational complexity of the Weisfeiler-Leman dimension
by: Lichter, Moritz, et al.
Published: (2024)

Depth-Bounds for Neural Networks via the Braid Arrangement
by: Grillo, Moritz, et al.
Published: (2025)

Parameterized Complexity of Segment Routing
by: Bazgan, Cristina, et al.
Published: (2025)

The Parameterized Complexity of Terminal Monitoring Set
by: Aravind, N. R., et al.
Published: (2024)

On the Incompressibility of Truth With Application to Circuit Complexity
by: Tonon, Luke
Published: (2025)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
by: Concha-Vega, Pablo, et al.
Published: (2025)

Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions
by: Tsui, Darin, et al.
Published: (2025)

Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
by: Bhore, Sujoy, et al.
Published: (2026)

Complexity of Boolean automata networks under block-parallel update modes
by: Perrot, Kévin, et al.
Published: (2024)

Nearest Neighbor Representations of Neurons
by: Kilic, Kordag Mehmet, et al.
Published: (2024)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

On the complexity of freezing automata networks of bounded pathwidth
by: Goles, Eric, et al.
Published: (2025)

Structural Origins of Cubic Complexity in Pebble Motion
by: Nakamigawa, Tomoki, et al.
Published: (2025)

A Unified Approach to Submodular Maximization Under Noise
by: Bhawalkar, Kshipra, et al.
Published: (2025)

Total Variation Distance Meets Probabilistic Inference
by: Bhattacharyya, Arnab, et al.
Published: (2023)

Complexity results for a cops and robber game on directed graphs
by: Ben-Ameur, Walid, et al.
Published: (2024)

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
by: Bok, Jan, et al.
Published: (2021)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
by: Nakajima, Tamio-Vesa, et al.
Published: (2025)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
by: Le, Hoang-Oanh, et al.
Published: (2023)

Edge-Disjoint Paths in Eulerian Digraphs
by: Cavallaro, Dario, et al.
Published: (2024)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Maximal Line Digraphs
by: Japhet, Quentin, et al.
Published: (2024)