Multiparty Karchmer-Wigderson Games and Threshold Circuits
Received: July 16, 2020
Revised: May 8, 2022
Published: June 12, 2022
Revised: May 8, 2022
Published: June 12, 2022
Keywords: Karchmer-Wigderson games, threshold circuits, threshold gates, majority function
Categories: complexity theory, circuit complexity, communication complexity, Karchmer-Wigderson games, majority, threshold, CCC, CCC 2020 special issue
ACM Classification: F.1.3, F.1.2
AMS Classification: 68Q17, 68Q25
Abstract: [Plain Text Version]
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.
Licensed under a Creative Commons Attribution License (CC-BY)