Image de couverture de livre

Reachability In Simple Neural Networks

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Sälzer, Marco, Lange, Martin
Format:	Preprint
Publié:	2022
Sujets:	Computational Complexity Machine Learning
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
par: Alsmann, Eric, et autres
Publié: (2026)

Verifying Quantized Graph Neural Networks is PSPACE-complete
par: Sälzer, Marco, et autres
Publié: (2025)

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
par: Sälzer, Marco, et autres
Publié: (2024)

The Reachability Problem for Neural-Network Control Systems
par: Schilling, Christian, et autres
Publié: (2024)

Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable
par: Chernobrovkin, Artem, et autres
Publié: (2025)

The Descriptive Complexity of Graph Neural Networks
par: Grohe, Martin
Publié: (2023)

Low-Rank Matrix Approximation for Neural Network Compression
par: Cherukuri, Kalyan, et autres
Publié: (2025)

Complexity of Injectivity and Verification of ReLU Neural Networks
par: Froese, Vincent, et autres
Publié: (2024)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
par: Cao, Yang, et autres
Publié: (2025)

On the Hardness of Learning One Hidden Layer Neural Networks
par: Li, Shuchen, et autres
Publié: (2024)

Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module
par: Oh, Yun-Tak, et autres
Publié: (2026)

Computational Complexity Evaluation of Neural Network Applications in Signal Processing
par: Freire, Pedro, et autres
Publié: (2022)

The Computational Complexity of Satisfiability in State Space Models
par: Alsmann, Eric, et autres
Publié: (2025)

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
par: Hertrich, Christoph, et autres
Publié: (2020)

Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
par: Bertschinger, Daniel, et autres
Publié: (2022)

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
par: Li, Xiaoyu, et autres
Publié: (2025)

Unlocking the Theory Behind Scaling 1-Bit Neural Networks
par: Daliri, Majid, et autres
Publié: (2024)

Parameterized Hardness of Zonotope Containment and Neural Network Verification
par: Froese, Vincent, et autres
Publié: (2025)

Provably Explaining Neural Additive Models
par: Bassan, Shahaf, et autres
Publié: (2026)

Neural Networks and (Virtual) Extended Formulations
par: Hertrich, Christoph, et autres
Publié: (2024)

Arithmetic Circuits and Neural Networks for Regular Matroids
par: Hertrich, Christoph, et autres
Publié: (2025)

Training Neural Networks is NP-Hard in Fixed Dimension
par: Froese, Vincent, et autres
Publié: (2023)

A Distributional-Lifting Theorem for PAC Learning
par: Blanc, Guy, et autres
Publié: (2025)

A Logic for Expressing Log-Precision Transformers
par: Merrill, William, et autres
Publié: (2022)

On the Hardness of Learning Regular Expressions
par: Attias, Idan, et autres
Publié: (2025)

Learnability of Parameter-Bounded Bayes Nets
par: Bhattacharyya, Arnab, et autres
Publié: (2024)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
par: Merrill, William, et autres
Publié: (2025)

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

Spiky Rank and Its Applications to Rigidity and Circuits
par: Hambardzumyan, Lianna, et autres
Publié: (2026)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
par: Li, Qian, et autres
Publié: (2026)

Proximity to Losslessly Compressible Parameters
par: Farrugia-Roberts, Matthew
Publié: (2023)

Decision Tree Learning on Product Spaces
par: Moakahr, Arshia Soltani, et autres
Publié: (2026)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
par: Amiri, Alireza, et autres
Publié: (2025)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
par: Wang, Jie, et autres
Publié: (2024)

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
par: Chandrasekaran, Gautam, et autres
Publié: (2024)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
par: Jacobs, Peter Matthew, et autres
Publié: (2026)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
par: Huang, Jizhou, et autres
Publié: (2025)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
par: Li, Zhiyuan, et autres
Publié: (2024)

From Pseudorandomness to Multi-Group Fairness and Back
par: Dwork, Cynthia, et autres
Publié: (2023)

Ask, and it shall be given: On the Turing completeness of prompting
par: Qiu, Ruizhong, et autres
Publié: (2024)