Circuit Complexity

Follow this topic Ask about this topic

Latest papers

13 papers0 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

On the Expressive Power of Transformers
Aug 13, 2026Phokion Kolaitis, Rik SenguptaTransformer Expressivity Circuit Complexity
University of California Santa Cruz Santa Cruz, CA · IBM Research Cambridge, MA
Tropical Circuits with Scalar Multiplication Gates
Jul 13, 2026Christoph Hertrich, Moritz StargallaNeural Network Expressivity Circuit Complexity
University of Technology Nuremberg
Exploring the Cryptographic Limits of Transformer Networks
Jun 28, 2026Stefan Domunco, Andis Draguns, Philip Torr +2Transformer Expressivity Circuit Complexity
University of Oxford · Contramont Research
FactorLibrary: From Polynomials to Circuits via Recursive Subgoals
Jun 24, 2026Rohan Pandey, Michael Ruofan Zeng, Weikun K. Zhang +5Circuit Discovery Reinforcement Learning
University of Washington, Seattle, WA, USA.
Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
May 28, 2026Anej Svete, William Merrill, Ryan Cotterell +1Transformer Expressivity Transformer
1. ETH Zürich · 2. Allen Institute for AI
The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems
May 21, 2026Dongxin GuoTransformer Expressivity Trust in AI
UNIVERSITY OF HONG KONG
A Measure-Theoretic Analysis of Reasoning in Transformers: Structural Generalization and Approximation Limits
May 19, 2026Yuyang Zhang, Yifu Zhang, Xuehai Zhou +1Transformer Expressivity OOD Generalization
McGill University · Mila - Quebec AI Institute · Université de Montréal
Average Attention Transformers and Arithmetic Circuits
May 6, 2026Lena Ehrmuth, Laura StriekerTransformer Expressivity Transformer
Institute for Theoretical Computer Science, Leibniz University Hanover, Hanover, Germany
Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers
Mar 25, 2026Naiming Liu, Richard Baraniuk, Shashank SonkarCircuit Complexity Knowledge Tracing
Rice University · University of Central Florida
Recurrent Graph Neural Networks and Arithmetic Circuits
Mar 5, 2026Timon Barlag, Vivian Holzapfel, Laura Strieker +2Circuit Complexity Graph Neural Networks
Institut für Theoretische Informatik, Leibniz Universität Hannover, Germany · School of Computing Science, University of Glasgow, UK
Why Are Linear RNNs More Parallelizable?
Mar 4, 2026William Merrill, Hongjian Jiang, Yanhong Li +2Circuit Complexity Recurrent Neural Networks
Allen Institute for AI · Rheinland-Pfälzische Technische Universität · Max-Planck Institute for Software Systems
Spiky Rank and Its Applications to Rigidity and Circuits
Feb 26, 2026Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov +2Circuit Complexity
The University of Copenhagen, Denmark. · EPFL, Switzerland. · Lund University, Sweden. +1
Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach
Nov 10, 2024Søren RiisCircuit Complexity Neural Network Expressivity
Centre for Fundamentals of AI and Computational Theory, Queen Mary University of London, London, United Kingdom.

Aug 13, 2026J/K move · Enter open · S save

On the Expressive Power of Transformers

Phokion Kolaitis, Rik Sengupta

University of California Santa Cruz Santa Cruz, CA · IBM Research Cambridge, MA

Transformer Expressivity Circuit Complexity

Open paper AskPDF arXiv

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.