Copertina

Spiky Rank and Its Applications to Rigidity and Circuits

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Hambardzumyan, Lianna, Myasnikov, Konstantin, Riazanov, Artur, Shirley, Morgan, Shraibman, Adi
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Log-Rank Conjecture: New Equivalent Formulations
di: Hambardzumyan, Lianna, et al.
Pubblicazione: (2025)

The Rank-Ramsey Problem and the Log-Rank Conjecture
di: Beniamini, Gal, et al.
Pubblicazione: (2024)

Sampling Permutations with Cell Probes is Hard
di: Alekseev, Yaroslav, et al.
Pubblicazione: (2025)

Factorization norms and an inverse theorem for MaxCut
di: Balla, Igor, et al.
Pubblicazione: (2025)

No Complete Problem for Constant-Cost Randomized Communication
di: Fang, Yuting, et al.
Pubblicazione: (2024)

Top-Down Lower Bounds for Depth-Four Circuits
di: Göös, Mika, et al.
Pubblicazione: (2023)

Partial Minimum Branching Program Size Problem is ETH-hard
di: Glinskih, Ludmila, et al.
Pubblicazione: (2024)

Monotone Circuit Complexity of Matching
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)

Better Boosting of Communication Oracles, or Not
di: Harms, Nathaniel, et al.
Pubblicazione: (2024)

Equality is Far Weaker than Constant-Cost Communication
di: Göös, Mika, et al.
Pubblicazione: (2025)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
di: Gryaznov, Svyatoslav, et al.
Pubblicazione: (2024)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
di: Riazanov, Artur, et al.
Pubblicazione: (2025)

Ranking Vectors Clustering: Theory and Applications
di: Fattahi, Ali, et al.
Pubblicazione: (2025)

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

New Hardness Results for Low-Rank Matrix Completion
di: Chawin, Dror, et al.
Pubblicazione: (2025)

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

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

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
di: Chukhin, Nikolai, et al.
Pubblicazione: (2024)

Pseudodeterministic Communication Complexity
di: Göös, Mika, et al.
Pubblicazione: (2025)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

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

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

Lossless Model Compression via Joint Low-Rank Factorization Optimization
di: Zhang, Boyang, et al.
Pubblicazione: (2024)

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

Sum of Squares Circuits
di: Loconte, Lorenzo, et al.
Pubblicazione: (2024)

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

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

Omnipredictors for Regression and the Approximate Rank of Convex Functions
di: Gopalan, Parikshit, et al.
Pubblicazione: (2024)

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

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

What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?
di: Xu, Ruihan, et al.
Pubblicazione: (2025)

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

Learning and Generating Mixed States Prepared by Shallow Channel Circuits
di: Hu, Fangjun, et al.
Pubblicazione: (2026)

Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
di: Gui, Kaiwen, et al.
Pubblicazione: (2023)

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

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
di: Lu, Yiyang, et al.
Pubblicazione: (2025)

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

Taming Barren Plateaus in Arbitrary Parameterized Quantum Circuits without Sacrificing Expressibility
di: Chen, Zhenyu, et al.
Pubblicazione: (2025)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
di: Alman, Josh, et al.
Pubblicazione: (2025)

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