Cover Image

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cao, Yang, Song, Zhao, Zhang, Jiahao, Zhao, Jiale
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
by: Chen, Yifang, et al.
Published: (2024)

Circuit Complexity Bounds for Visual Autoregressive Model
by: Ke, Yekun, et al.
Published: (2025)

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

On Fine-Grained I/O Complexity of Attention Backward Passes
by: Li, Xiaoyu, et al.
Published: (2024)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
by: Chen, Bo, et al.
Published: (2024)

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

Fundamental Limitations on Subquadratic Alternatives to Transformers
by: Alman, Josh, et al.
Published: (2024)

Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
by: Chen, Bo, et al.
Published: (2025)

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks
by: Rosenbluth, Eran
Published: (2026)

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

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

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
by: Cao, Yang, et al.
Published: (2024)

Reachability In Simple Neural Networks
by: Sälzer, Marco, et al.
Published: (2022)

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

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

On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
by: Ke, Yekun, et al.
Published: (2025)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)

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

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
by: Hu, Jerry Yao-Chieh, et al.
Published: (2024)

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

On Computational Limits of FlowAR Models: Expressivity and Efficiency
by: Cao, Yang, et al.
Published: (2025)

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

Local vs. Global Interpretability: A Computational Complexity Perspective
by: Bassan, Shahaf, et al.
Published: (2024)

RoPE Attention Can Be Trained in Almost Linear Time
by: Cao, Yang, et al.
Published: (2024)

Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2024)

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

Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory
by: Zubić, Nikola, et al.
Published: (2024)

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

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
by: Jacot, Arthur
Published: (2025)

Additive Models Explained: A Computational Complexity Approach
by: Bassan, Shahaf, et al.
Published: (2025)

Recurrent Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2026)

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

Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
by: Zhang, Zhihan, et al.
Published: (2024)

InstaHide's Sample Complexity When Mixing Two Private Images
by: Huang, Baihe, et al.
Published: (2020)

When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
by: Li, Chenyang, et al.
Published: (2025)

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

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

Looped ReLU MLPs May Be All You Need as Practical Programmable Computers
by: Liang, Yingyu, et al.
Published: (2024)

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