Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Natalia Dobrokhotova-Maikova:

TR23-153 | 19th October 2023
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

Towards Simpler Sorting Networks and Monotone Circuits for Majority

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 both the classical setting with elementary operations of arity $2$ and the generalized setting with operations of arity $k$, where $k$ is a ... more >>>

TR22-116 | 17th August 2022
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

Constant-Depth Sorting Networks

In this paper, we address sorting networks that are constructed from comparators of arity $k > 2$. That is, in our setting the arity of the comparators -- or, in other words, the number of inputs that can be sorted at the unit cost -- is a parameter. We study ... more >>>

ISSN 1433-8092 | Imprint