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

Aniruddha Biswas, Palash Sarkar

We show that the ''majority is least stable'' conjecture is true for $n=1$ and $3$ and false for all odd $n\geq 5$.

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