Image de couverture de livre

Subquadratic Algorithms and Hardness for Attention with Any Temperature

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Gupta, Shreya, Huang, Boyang, Saha, Barna, Xu, Yinzhan, Ye, Christopher
Format:	Preprint
Publié:	2025
Sujets:	Machine Learning Computational Complexity F.2.1
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On the Computational Hardness of Transformers
par: Saha, Barna, et autres
Publié: (2026)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
par: Saha, Barna, et autres
Publié: (2024)

Algorithmic hardness of the partition function for nucleic acid strands
par: Ducloz, Gwendal, et autres
Publié: (2025)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
par: Pavlov, Gorgi
Publié: (2026)

The Structural Complexity of Matrix-Vector Multiplication
par: Anand, Emile, et autres
Publié: (2025)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
par: Saha, Barna, et autres
Publié: (2024)

Polynomial-time Tractable Problems over the $p$-adic Numbers
par: Fehm, Arno, et autres
Publié: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
par: Anand, Emile, et autres
Publié: (2024)

Small Shadow Partitions
par: Kopparty, Swastik, et autres
Publié: (2024)

On Sampling Lower Bounds for Polynomials
par: Khodabandeh, Mohammad Mahdi, et autres
Publié: (2026)

PosSLP and Sum of Squares
par: Bläser, Markus, et autres
Publié: (2024)

Average Attention Transformers and Arithmetic Circuits
par: Ehrmuth, Lena, et autres
Publié: (2026)

Symmetric Arithmetic Circuits
par: Dawar, Anuj, et autres
Publié: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
par: Dawar, Anuj, et autres
Publié: (2021)

When Votes Change and Committees Should (Not)
par: Bredereck, Robert, et autres
Publié: (2020)

Col is PSPACE-complete on Triangular Grids
par: Burke, Kyle, et autres
Publié: (2025)

The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication
par: Murthy, Sandeep
Publié: (2007)

On the Computation of 2-Dimensional Recurrence Equations
par: Natale, Giuseppe
Publié: (2024)

Completeness classes in algebraic complexity theory
par: Bürgisser, Peter
Publié: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
par: Conneryd, Jonas, et autres
Publié: (2025)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
par: de Rezende, Susanna F., et autres
Publié: (2024)

Eliminating Illusion in Directed Networks
par: Jana, Sougata, et autres
Publié: (2026)

Realizable Circuit Complexity: Embedding Computation in Space-Time
par: Prada, Benjamin, et autres
Publié: (2025)

Graph Neural Networks and Arithmetic Circuits
par: Barlag, Timon, et autres
Publié: (2024)

Recurrent Graph Neural Networks and Arithmetic Circuits
par: Barlag, Timon, et autres
Publié: (2026)

Replicability in High Dimensional Statistics
par: Hopkins, Max, et autres
Publié: (2024)

Fundamental Limitations on Subquadratic Alternatives to Transformers
par: Alman, Josh, et autres
Publié: (2024)

Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
par: Koiran, Pascal, et autres
Publié: (2022)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
par: Salas, Jesus
Publié: (2025)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
par: Burke, Kyle, et autres
Publié: (2025)

Dichotomy for orderings?
par: Kun, Gábor, et autres
Publié: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
par: Edwards, Darren J.
Publié: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
par: Kumar, Mrinal, et autres
Publié: (2018)

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

Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity
par: Gupta, Chetan, et autres
Publié: (2024)

Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic
par: Paszyński, Maciej
Publié: (2024)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
par: Lela, Marko
Publié: (2025)

Two-Sided Lossless Expanders in the Unbalanced Setting
par: Chattopadhyay, Eshan, et autres
Publié: (2024)

Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework
par: Lee, Changryeol
Publié: (2026)

Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization
par: Liao, Junyi, et autres
Publié: (2026)