2 citations · 2 across the 5 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…