Theory of Computing
-------------------
Title     : Multiparty Karchmer-Wigderson Games and Threshold Circuits
Authors   : Alexander Kozachinskiy and Vladimir Podolskii
Volume    : 18
Number    : 15
Pages     : 1-33
URL       : https://theoryofcomputing.org/articles/v018a015

Abstract
--------

We propose a generalization of the 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 formula for the Majority function,
consisting only of 3-bit majority gates and variables. This resolves a
conjecture of Cohen et al. (CRYPTO'13).

----------------

A conference version of this paper appeared in the Proceedings of
the 35th Computational Complexity Conference, 2020.