2 papers
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.CC2022
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…