2 citations · 2 across the 6 of their papers we have counts for
5 papers
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…
Inapproximability of sufficient reasons for decision trees
Alexander Kozachinskiy
In this note, we establish the hardness of approximation of the problem of computing the minimal size of a -sufficient reason for decision trees.
Find a witness or shatter: the landscape of computable PAC learning
Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas +1
This paper contributes to the study of CPAC learnability -- a computable version of PAC learning -- by solving three open questions from recent papers. Firstly, we prove that every…
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…