Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexander Kozachinskiy:

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 >>>

ISSN 1433-8092 | Imprint