8 citations · 28 across the 19 of their papers we have counts for
24 papers
VC Dimension and Expressivity of Real-Valued Transformers
Gavin Dooley, Andy Yang, Yijia Jessica Zhu +3
Whereas previous results on abilities and limitations of transformers have restricted the definition of transformers in various ways, here we study softmax-attention, multi-layer t…
Tighter Bounds on the Expressivity of Transformer Encoders
David Chiang, Peter Cholak, Anand Pillay
Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for t…
Overcoming a Theoretical Limitation of Self-Attention
David Chiang, Peter Cholak
Although transformers are remarkably effective for many tasks, there are some surprisingly easy-looking regular languages that they struggle with. Hahn shows that for languages whe…
Extending Properly n-REA Sets
Peter A. Cholak, Peter M. Gerdes
In [5] Soare and Stob prove that if is an r.e. set which isn't computable then there is a set of the form which isn't of r.e. Turing degree. If we define a pro…
Realizing Computably Enumerable Degrees in Separating Classes
Peter Cholak, Rod Downey, Noam Greenberg +1
We investigate what collections of c.e.\ Turing degrees can be realised as the collection of elements of a separating class of c.e.\ degree. We show that for every c.e.\ de…
Milliken's tree theorem and its applications: a computability-theoretic perspective
Paul-Elliot Anglès d'Auriac, Peter A. Cholak, Damir D. Dzhafarov +2
Milliken's tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey's theorem and its many variants and co…