Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-017 | 19th July 2020 13:11

Multiparty Karchmer-Wigderson Games and Threshold Circuits

RSS-Feed




Revision #1
Authors: Alexander Kozachinskiy, Vladimir Podolskii
Accepted on: 19th July 2020 13:11
Downloads: 429
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).



Changes to previous version:

We added a direct exposition of our explicit logarihmic-depth MAJ_3-formula for Majority function to Appendix.


Paper:

TR20-017 | 18th February 2020 11:07

Multiparty Karchmer-Wigderson Games and Threshold Circuits





TR20-017
Authors: Alexander Kozachinskiy, Vladimir Podolskii
Publication: 18th February 2020 20:24
Downloads: 794
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