Fetching the paper…
Reading the bibliography…
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 TC$^0$.
The Boolean formula value problem is in ALOGTIME
Samuel R. Buss · 1987
Earlier work this paper cites.
On uniformity within 𝑁𝐶 1 \mathit{NC^{1}}
David A. Mix Barrington, Neil Immerman, and Howard Straubing · 1990
Earlier work this paper cites.
Regular languages in 𝑁𝐶 1 \mathit{NC^{1}}
David A. Barrington, Kevin Compton, Howard Straubing, and Denis Thérien · 1992
Earlier work this paper cites.
Modular temporal logic
Augustin Baziramwabo, Pierre McKenzie, and Denis Thérien · 1999
Earlier work this paper cites.
Descriptive Complexity
Neil Immerman · 1999
Earlier work this paper cites.
Advanced course on computational complexity, 2000
David Mix Barrington and Alexis Maciel · 2000
Earlier work this paper cites.
Uniform constant-depth threshold circuits for division and iterated multiplication
William Hesse, Eric Allender, and David A. Mix Barrington · 2002
Earlier work this paper cites.
Root finding with threshold circuits
Emil Jeřábek · 2012
Earlier work this paper cites.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton · 2016
Cited alongside, same era.
Computer arithmetic, 2017
David Goldberg · 2017
Cited alongside, same era.
Attention is all you need
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin · 2017
Cited alongside, same era.
On the Turing completeness of modern neural network architectures
Jorge Pérez, Javier Marinković, and Pablo Barceló · 2019
Cited alongside, same era.
Theoretical limitations of self-attention in neural sequence models
Michael Hahn · 2020
Cited alongside, same era.
Self-attention networks can process bounded hierarchical languages
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan · 2021
Tighter bounds on the expressivity of transformer encoders
David Chiang, Peter Cholak, and Anand Pillay · 2023
Later among the works it cites.
Transformers learn shortcuts to automata
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang · 2023
Later among the works it cites.
A logic for expressing log-precision transformers
William Merrill and Ashish Sabharwal · 2023
Later among the works it cites.
Average-hard attention transformers are constant-depth uniform threshold circuits, 2023
Lena Strobl · 2023
Later among the works it cites.
Logical languages accepted by transformer encoders with hard attention
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir Podolskii · 2024
Closest in time.
Chain of thought empowers transformers to solve inherently serial problems
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Saturated transformers are constant-depth threshold circuits
William Merrill, Ashish Sabharwal, and Noah A. Smith · 2022
Cited alongside, same era.
Some estimated likelihoods for computational complexity
R. Ryan Williams · 2022
Cited alongside, same era.
The parallelism tradeoff: Limitations of log-precision transformers
William Merrill and Ashish Sabharwal
Cited in the paper.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma · 2024
Closest in time.
What formal languages can transformers express? A survey
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin · 2024
Closest in time.
Counting like transformers: Compiling temporal counting logic into softmax transformers
Andy Yang and David Chiang · 2024
Closest in time.