Peter Cholak

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 transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform $TC^0$. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.

Peter Cholak, Marianna Csörnyei, Neil Lutz et al.

We introduce a new technique for proving bounds on the Kolmogorov complexity of geometric objects in Euclidean space, such as points and lines. We apply this technique to prove two theorems on algorithmic information theory, both of which have consequences for well-known problems in geometric measure theory. First, we show that for any point $x$ in the plane and any other point $y$ sufficiently independent of $x$, the distance between $x$ and $y$ retains at least half the complexity of the original point $x$. By the point-to-set principle of J. Lutz and N. Lutz, this yields an improved lower bound on the Hausdorff dimension of pinned distance sets, a topic closely related to Falconer's distance set conjecture. Second, we prove an analogous result for orthogonal projections: for any point $x$ in the plane and any line through the origin which is sufficiently independent of $x$, the projection of $x$ onto that line retains at least half the complexity of $x$. As a consequence, we obtain a generalization of a theorem of Bourgain on exceptional sets for orthogonal projections.

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 where acceptance depends on a single input symbol, a transformer's classification decisions become less and less confident (that is, with cross-entropy approaching 1 bit per string) as input strings get longer and longer. We examine this limitation using two languages: PARITY, the language of bit strings with an odd number of 1s, and FIRST, the language of bit strings starting with a 1. We demonstrate three ways of overcoming the limitation suggested by Hahn's lemma. First, we settle an open question by constructing a transformer that recognizes PARITY with perfect accuracy, and similarly for FIRST. Second, we use layer normalization to bring the cross-entropy of both models arbitrarily close to zero. Third, when transformers need to focus on a single position, as for FIRST, we find that they can fail to generalize to longer strings; we offer a simple remedy to this problem that also improves length generalization in machine translation.