2 citations · 2 across the 5 of their papers we have counts for
6 papers
Polynomial-Time Mistake-Bounded Language Generation
Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo
In this paper, we introduce a polynomial-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold (2026). We obtain upper and…
The Counting Power of Transformers
Marco Sälzer, Chris Köcher, Alexander Kozachinskiy +2
Counting properties (e.g. determining whether certain tokens occur more than other tokens in a given input text) have played a significant role in the study of expressiveness of tr…
Towards Simpler Sorting Networks and Monotone Circuits for Majority
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii
In this paper, we study the problem of computing the majority function by low-depth monotone circuits and a related problem of constructing low-depth sorting networks. We consider…
Logical Languages Accepted by Transformer Encoders with Hard Attention
Pablo Barcelo, Alexander Kozachinskiy, Anthony Widjaja Lin +1
We contribute to the study of formal languages that can be recognized by transformer encoders. We focus on two self-attention mechanisms: (1) UHAT (Unique Hard Attention Transforme…
Constant-Depth Sorting Networks
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii
In this paper, we address sorting networks that are constructed from comparators of arity . That is, in our setting the arity of the comparators -- or, in other words, the n…
Multiparty Karchmer-Wigderson Games and Threshold Circuits
Alexander Kozachinskiy, Vladimir Podolskii
We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of thre…