2026-07-22T04:18:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12576 2024-03-06T10:50:29Z ddc:004 open_access

Multiparty Karchmer - Wigderson Games and Threshold Circuits Kozachinskiy, Alexander Podolskii, Vladimir Karchmer-Wigderson Games Threshold Circuits threshold gates majority function 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Kozachinskiy and Vladimir Podolskii 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.24 urn:nbn:de:0030-drops-125767 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.24 eng https://creativecommons.org/licenses/by/3.0/legalcode