2 citations · 2 across the 5 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.CC2023
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…
cs.FL2023★ 2 cited
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…