Gespeichert in:
| Hauptverfasser: | Cao, Yang, Song, Zhao, Zhang, Jiahao, Zhao, Jiale |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2510.05494 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Ähnliche Einträge
On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
von: Li, Xiaoyu, et al.
Veröffentlicht: (2025)
von: Li, Xiaoyu, et al.
Veröffentlicht: (2025)
The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
von: Chen, Yifang, et al.
Veröffentlicht: (2024)
von: Chen, Yifang, et al.
Veröffentlicht: (2024)
Circuit Complexity Bounds for Visual Autoregressive Model
von: Ke, Yekun, et al.
Veröffentlicht: (2025)
von: Ke, Yekun, et al.
Veröffentlicht: (2025)
On Fine-Grained I/O Complexity of Attention Backward Passes
von: Li, Xiaoyu, et al.
Veröffentlicht: (2024)
von: Li, Xiaoyu, et al.
Veröffentlicht: (2024)
The Descriptive Complexity of Graph Neural Networks
von: Grohe, Martin
Veröffentlicht: (2023)
von: Grohe, Martin
Veröffentlicht: (2023)
Circuit Complexity Bounds for RoPE-based Transformer Architecture
von: Chen, Bo, et al.
Veröffentlicht: (2024)
von: Chen, Bo, et al.
Veröffentlicht: (2024)
Unlocking the Theory Behind Scaling 1-Bit Neural Networks
von: Daliri, Majid, et al.
Veröffentlicht: (2024)
von: Daliri, Majid, et al.
Veröffentlicht: (2024)
Fundamental Limitations on Subquadratic Alternatives to Transformers
von: Alman, Josh, et al.
Veröffentlicht: (2024)
von: Alman, Josh, et al.
Veröffentlicht: (2024)
Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
von: Chen, Bo, et al.
Veröffentlicht: (2025)
von: Chen, Bo, et al.
Veröffentlicht: (2025)
Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks
von: Rosenbluth, Eran
Veröffentlicht: (2026)
von: Rosenbluth, Eran
Veröffentlicht: (2026)
Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
von: Cao, Yang, et al.
Veröffentlicht: (2024)
von: Cao, Yang, et al.
Veröffentlicht: (2024)
On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
von: Ke, Yekun, et al.
Veröffentlicht: (2025)
von: Ke, Yekun, et al.
Veröffentlicht: (2025)
On Computational Limits of FlowAR Models: Expressivity and Efficiency
von: Cao, Yang, et al.
Veröffentlicht: (2025)
von: Cao, Yang, et al.
Veröffentlicht: (2025)
The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
von: Alman, Josh, et al.
Veröffentlicht: (2024)
von: Alman, Josh, et al.
Veröffentlicht: (2024)
The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
von: Alsmann, Eric, et al.
Veröffentlicht: (2026)
von: Alsmann, Eric, et al.
Veröffentlicht: (2026)
Complexity of Injectivity and Verification of ReLU Neural Networks
von: Froese, Vincent, et al.
Veröffentlicht: (2024)
von: Froese, Vincent, et al.
Veröffentlicht: (2024)
Arithmetic Circuits and Neural Networks for Regular Matroids
von: Hertrich, Christoph, et al.
Veröffentlicht: (2025)
von: Hertrich, Christoph, et al.
Veröffentlicht: (2025)
Computational Complexity Evaluation of Neural Network Applications in Signal Processing
von: Freire, Pedro, et al.
Veröffentlicht: (2022)
von: Freire, Pedro, et al.
Veröffentlicht: (2022)
Verifying Quantized Graph Neural Networks is PSPACE-complete
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)
Graph Neural Networks and Arithmetic Circuits
von: Barlag, Timon, et al.
Veröffentlicht: (2024)
von: Barlag, Timon, et al.
Veröffentlicht: (2024)
Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
von: Hu, Jerry Yao-Chieh, et al.
Veröffentlicht: (2024)
von: Hu, Jerry Yao-Chieh, et al.
Veröffentlicht: (2024)
RoPE Attention Can Be Trained in Almost Linear Time
von: Cao, Yang, et al.
Veröffentlicht: (2024)
von: Cao, Yang, et al.
Veröffentlicht: (2024)
Reachability In Simple Neural Networks
von: Sälzer, Marco, et al.
Veröffentlicht: (2022)
von: Sälzer, Marco, et al.
Veröffentlicht: (2022)
Local vs. Global Interpretability: A Computational Complexity Perspective
von: Bassan, Shahaf, et al.
Veröffentlicht: (2024)
von: Bassan, Shahaf, et al.
Veröffentlicht: (2024)
Recurrent Graph Neural Networks and Arithmetic Circuits
von: Barlag, Timon, et al.
Veröffentlicht: (2026)
von: Barlag, Timon, et al.
Veröffentlicht: (2026)
Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
von: Huang, Zekai, et al.
Veröffentlicht: (2025)
von: Huang, Zekai, et al.
Veröffentlicht: (2025)
Spiky Rank and Its Applications to Rigidity and Circuits
von: Hambardzumyan, Lianna, et al.
Veröffentlicht: (2026)
von: Hambardzumyan, Lianna, et al.
Veröffentlicht: (2026)
Nearest Neighbor Representations of Neural Circuits
von: Kilic, Kordag Mehmet, et al.
Veröffentlicht: (2024)
von: Kilic, Kordag Mehmet, et al.
Veröffentlicht: (2024)
Low-Rank Matrix Approximation for Neural Network Compression
von: Cherukuri, Kalyan, et al.
Veröffentlicht: (2025)
von: Cherukuri, Kalyan, et al.
Veröffentlicht: (2025)
Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory
von: Zubić, Nikola, et al.
Veröffentlicht: (2024)
von: Zubić, Nikola, et al.
Veröffentlicht: (2024)
Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit
von: Rosenbluth, Eran, et al.
Veröffentlicht: (2025)
von: Rosenbluth, Eran, et al.
Veröffentlicht: (2025)
Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
von: Jacot, Arthur
Veröffentlicht: (2025)
von: Jacot, Arthur
Veröffentlicht: (2025)
InstaHide's Sample Complexity When Mixing Two Private Images
von: Huang, Baihe, et al.
Veröffentlicht: (2020)
von: Huang, Baihe, et al.
Veröffentlicht: (2020)
Additive Models Explained: A Computational Complexity Approach
von: Bassan, Shahaf, et al.
Veröffentlicht: (2025)
von: Bassan, Shahaf, et al.
Veröffentlicht: (2025)
Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
von: Zhang, Zhihan, et al.
Veröffentlicht: (2024)
von: Zhang, Zhihan, et al.
Veröffentlicht: (2024)
When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
von: Li, Chenyang, et al.
Veröffentlicht: (2025)
von: Li, Chenyang, et al.
Veröffentlicht: (2025)
The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
von: Stargalla, Moritz, et al.
Veröffentlicht: (2025)
von: Stargalla, Moritz, et al.
Veröffentlicht: (2025)
Realizable Circuit Complexity: Embedding Computation in Space-Time
von: Prada, Benjamin, et al.
Veröffentlicht: (2025)
von: Prada, Benjamin, et al.
Veröffentlicht: (2025)
Unifying Formal Explanations: A Complexity-Theoretic Perspective
von: Bassan, Shahaf, et al.
Veröffentlicht: (2026)
von: Bassan, Shahaf, et al.
Veröffentlicht: (2026)
On the Hardness of Learning One Hidden Layer Neural Networks
von: Li, Shuchen, et al.
Veröffentlicht: (2024)
von: Li, Shuchen, et al.
Veröffentlicht: (2024)
Ähnliche Einträge
-
On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
von: Li, Xiaoyu, et al.
Veröffentlicht: (2025) -
The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
von: Chen, Yifang, et al.
Veröffentlicht: (2024) -
Circuit Complexity Bounds for Visual Autoregressive Model
von: Ke, Yekun, et al.
Veröffentlicht: (2025) -
On Fine-Grained I/O Complexity of Attention Backward Passes
von: Li, Xiaoyu, et al.
Veröffentlicht: (2024) -
The Descriptive Complexity of Graph Neural Networks
von: Grohe, Martin
Veröffentlicht: (2023)