mlsanityData to 7 Oct 2026

Transformers in Uniform TC0

arXiv 2409.13629 ↗First posted 20 Sep 2024cs.CC cs.FL cs.LGcited by 25

Not on the map. Why?

Abstract (arXiv)

Previous work has shown that the languages recognized by average-hard attention transformers (AHATs) and softmax-attention transformers (SMATs) are within the circuit complexity class TC0. However, these results assume limited-precision arithmetic: using floating-point numbers with O(log n) bits (where n is the length of the input string), Strobl showed that AHATs can be approximated in L-uniform TC0, and Merrill and Sabharwal showed that SMATs can be approximated in DLOGTIME-uniform TC0. Here, we improve these results, showing that AHATs with no approximation, SMATs with O(poly(n)) bits of floating-point precision, and SMATs with at most 2-O(poly(n)) absolute error are all in DLOGTIME-uniform TC0.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 20 Sep 2024.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 8; 2026: 14.

25 papers.

Sort:

By area:

  1. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  2. 2025Exact Expressive Power of Transformers with Paddingcited by 19
  3. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  4. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  5. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 12
  6. 2024Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problemscited by 9
  7. 2025Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformerscited by 8
  8. 2026Why Are Linear RNNs More Parallelizable?cited by 7
  9. 2025Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteriacited by 5
  10. 2025On the Existence of Universal Simulators of Attentioncited by 1
  11. 2025Realizable Circuit Complexity: Embedding Computation in Space-Timecited by 1
  12. 2026Certifiable Boolean Reasoning Is Universalcited by 1
13 more
  1. 2026Dynamical Systems Theory Behind a Hierarchical Reasoning Modelcited by 1
  2. 2026Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don'tcited by 1
  3. 2026Comparing Transformers and Hybrid Models at the Token Levelcited by 1
  4. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0
  5. 2026Semantic Content Determines Algorithmic Performancecited by 0
  6. 2026Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformerscited by 0
  7. 2026Statistical Guarantees for Reasoning Probes on Looped Boolean Circuitscited by 0
  8. 2026Rational Transductorscited by 0
  9. 2026How Many Different Outputs Can a Transformer Generate?cited by 0
  10. 2026Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrizationcited by 0
  11. 2026A First-Principles Theory of Slow Thinking and Active Perceptioncited by 0
  12. 2026On the Expressive Power of Transformerscited by 0
  13. 2026Length Generalization for Transformers via Compressioncited by 0