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:

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

TR20-017 | 18th February 2020
Alexander Kozachinskiy, Vladimir Podolskii

Multiparty Karchmer-Wigderson Games and Threshold Circuits

Revisions: 1

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 threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>>

ISSN 1433-8092 | Imprint