License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.24
URN: urn:nbn:de:0030-drops-125767
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12576/
Go to the corresponding LIPIcs Volume Portal

Kozachinskiy, Alexander ; Podolskii, Vladimir

Multiparty Karchmer - Wigderson Games and Threshold Circuits

pdf-format:
LIPIcs-CCC-2020-24.pdf (0.5 MB)

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).

BibTeX - Entry

@InProceedings{kozachinskiy_et_al:LIPIcs:2020:12576,
  author =	{Alexander Kozachinskiy and Vladimir Podolskii},
  title =	{{Multiparty Karchmer - Wigderson Games and Threshold Circuits}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Shubhangi Saraf},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12576},
  URN =		{urn:nbn:de:0030-drops-125767},
  doi =		{10.4230/LIPIcs.CCC.2020.24},
  annote =	{Keywords: Karchmer-Wigderson Games, Threshold Circuits, threshold gates, majority function}
}

Keywords: Karchmer-Wigderson Games, Threshold Circuits, threshold gates, majority function
Collection: 35th Computational Complexity Conference (CCC 2020)
Issue Date: 2020
Date of publication: 17.07.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI