Document Open Access Logo

Multiparty Karchmer - Wigderson Games and Threshold Circuits

Authors Alexander Kozachinskiy , Vladimir Podolskii

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.24.pdf
  • Filesize: 0.54 MB
  • 23 pages

Document Identifiers

Author Details

Alexander Kozachinskiy
  • Department of Computer Science, University of Warwick, Coventry, UK
Vladimir Podolskii
  • Steklov Mathematical Institute, Russian Academy of Sciences, Moscow, Russia

Funding

  • Kozachinskiy, Alexander: Supported by the EPSRC grant EP/P020992/1 (Solving Parity Games in Theory and Practice).
  • Podolskii, Vladimir: The work of V.V. Podolskii was performed at the Steklov International Mathematical Center and supported by the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-15-2019-1614).

Acknowledgements

The authors are grateful to Alexander Shen for suggesting to generalize our initial results.

Cite AsGet BibTex

Alexander Kozachinskiy and Vladimir Podolskii. Multiparty Karchmer - Wigderson Games and Threshold Circuits. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.24

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

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • Karchmer-Wigderson Games
  • Threshold Circuits
  • threshold gates
  • majority function

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Miklós Ajtai, János Komlós, and Endre Szemerédi. An 0 (n log n) sorting network. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 1-9, 1983. URL: https://doi.org/10.1145/800061.808726.
  2. Gerth Stølting Brodal and Thore Husfeldt. A communication complexity proof that symmetric functions have logarithmic depth. BRICS, Department of Computer Science, Univ., 1996. Google Scholar
  3. Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, and Ron D Rothblum. Efficient multiparty protocols via log-depth threshold formulae. In Annual Cryptology Conference, pages 185-202. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40084-1_11.
  4. Irit Dinur and Or Meir. Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity. computational complexity, 27(3):375-462, 2018. URL: https://doi.org/10.1007/s00037-017-0159-x.
  5. Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson. Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 213-222, 2014. URL: https://doi.org/10.1145/2591796.2591856.
  6. Oded Goldreich. Valiant’s polynomial-size monotone formula for majority, 2011. URL: http://www.wisdom.weizmann.ac.il/~oded/PDF/mono-maj.pdf.
  7. Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 847-856, 2014. URL: https://doi.org/10.1145/2591796.2591838.
  8. Arvind Gupta and Sanjeev Mahajan. Using amplification to compute majority with small majority gates. Computational Complexity, 6(1):46-63, 1996. URL: https://doi.org/10.1007/BF01202041.
  9. Stasys Jukna. Boolean function complexity: advances and frontiers, volume 27. Springer Science &Business Media, 2012. URL: https://doi.org/10.1007/978-3-642-24508-4.
  10. Mauricio Karchmer, Ran Raz, and Avi Wigderson. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity, 5(3-4):191-204, 1995. URL: https://doi.org/10.1007/BF01206317.
  11. Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255-265, 1990. URL: https://doi.org/10.1137/0403021.
  12. Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. URL: https://doi.org/10.1017/9781108671644.
  13. Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 234-243. IEEE, 1997. URL: https://doi.org/10.1109/SFCS.1997.646112.
  14. Dmitry Sokolov. Dag-like communication and its applications. In International Computer Science Symposium in Russia, pages 294-307. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-58747-9_26.
  15. Leslie G. Valiant. Short monotone formulae for the majority function. Journal of Algorithms, 5(3):363-366, 1984. URL: https://doi.org/10.1016/0196-6774(84)90016-6.
  16. Ingo Wegener. The complexity of Boolean functions. BG Teubner, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact