:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Sälzer, Marco, Lange, Martin
Format:	Preprint
Published:	2022
Subjects:	Computational Complexity Machine Learning
Online Access:	https://arxiv.org/abs/2203.07941
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
by: Alsmann, Eric, et al.
Published: (2026)

Verifying Quantized Graph Neural Networks is PSPACE-complete
by: Sälzer, Marco, et al.
Published: (2025)

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
by: Sälzer, Marco, et al.
Published: (2024)

The Reachability Problem for Neural-Network Control Systems
by: Schilling, Christian, et al.
Published: (2024)

Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable
by: Chernobrovkin, Artem, et al.
Published: (2025)

The Descriptive Complexity of Graph Neural Networks
by: Grohe, Martin
Published: (2023)

Complexity of Injectivity and Verification of ReLU Neural Networks
by: Froese, Vincent, et al.
Published: (2024)

Low-Rank Matrix Approximation for Neural Network Compression
by: Cherukuri, Kalyan, et al.
Published: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
by: Cao, Yang, et al.
Published: (2025)

Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module
by: Oh, Yun-Tak, et al.
Published: (2026)

The Computational Complexity of Satisfiability in State Space Models
by: Alsmann, Eric, et al.
Published: (2025)

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

On the Hardness of Learning One Hidden Layer Neural Networks
by: Li, Shuchen, et al.
Published: (2024)

Computational Complexity Evaluation of Neural Network Applications in Signal Processing
by: Freire, Pedro, et al.
Published: (2022)

Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
by: Bertschinger, Daniel, et al.
Published: (2022)

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
by: Li, Xiaoyu, et al.
Published: (2025)

Unlocking the Theory Behind Scaling 1-Bit Neural Networks
by: Daliri, Majid, et al.
Published: (2024)

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

Provably Explaining Neural Additive Models
by: Bassan, Shahaf, et al.
Published: (2026)

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)

Training Neural Networks is NP-Hard in Fixed Dimension
by: Froese, Vincent, et al.
Published: (2023)

Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit
by: Rosenbluth, Eran, et al.
Published: (2025)

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs
by: Bournez, Olivier
Published: (2026)

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

Samplability makes learning easier
by: Blanc, Guy, et al.
Published: (2025)

ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
by: Hertrich, Christoph, et al.
Published: (2021)

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
by: Huang, Zekai, et al.
Published: (2025)

A Logic for Expressing Log-Precision Transformers
by: Merrill, William, et al.
Published: (2022)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

Learnability of Parameter-Bounded Bayes Nets
by: Bhattacharyya, Arnab, et al.
Published: (2024)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
by: Merrill, William, et al.
Published: (2025)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

Proximity to Losslessly Compressible Parameters
by: Farrugia-Roberts, Matthew
Published: (2023)

Decision Tree Learning on Product Spaces
by: Moakahr, Arshia Soltani, et al.
Published: (2026)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
by: Amiri, Alireza, et al.
Published: (2025)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
by: Wang, Jie, et al.
Published: (2024)