Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-017 | 18th February 2020 11:07

Multiparty Karchmer-Wigderson Games and Threshold Circuits

RSS-Feed




TR20-017
Authors: Alexander Kozachinskiy, Vladimir Podolskii
Publication: 18th February 2020 20:24
Downloads: 180
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint