Document Open Access Logo

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games

Authors Artur Ignatiev , Ivan Mihajlin, Alexander Smal

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2022.66.pdf
  • Filesize: 0.76 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • communication complexity
  • circuit complexity
  • Karchmer-Wigderson games

Metrics

Abstract

In this paper, we prove a super-cubic lower bound on the size of a communication protocol for generalized Karchmer-Wigderson game for an explicit function f: {0,1}ⁿ → {0,1}^{log n}. Lower bounds for original Karchmer-Wigderson games correspond to De Morgan formula lower bounds, thus the best known size lower bound is cubic. The generalized Karchmer-Wigderson games are similar to the original ones, so we hope that our approach can provide an insight for proving better lower bounds on the original Karchmer-Wigderson games, and hence for proving new lower bounds on De Morgan formula size.
To achieve super-cubic lower bound we adapt several techniques used in formula complexity to communication protocols, prove communication complexity lower bound for a composition of several functions with a multiplexer relation, and use a technique from [Ivan Mihajlin and Alexander Smal, 2021] to extract the "hardest" function from it. As a result, in this setting we are able to show that there is a relatively small set of functions such that at least one of them does not have a small protocol. The resulting lower bound of Ω̃(n^3.156) is significantly better than the bound obtained from the counting argument.

Cite As Get BibTex

Artur Ignatiev, Ivan Mihajlin, and Alexander Smal. Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.66

Author Details

Artur Ignatiev
  • St.Petersburg State University, Russia
  • HSE University, St.Petersburg, Russia
Ivan Mihajlin
  • St.Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, Russia
Alexander Smal
  • St.Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, Russia
  • Technion, Haifa, Israel

Funding

  • Ignatiev, Artur: The chapters 1-2 were supported by the Ministry of Science and Higher Education of the Russian Federation, agreement 075-15-2019-1620 date 08/11/2019 and 075-15-2022-289 date 06/04/2022. The chapters 3-4 were supported by the Basic Research Program and the "Priority 2030" program at HSE University.
  • Smal, Alexander: Received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement numero 802020-ERC-HARMONIC.

References

  1. Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, and Mikhail Ushakov. New bounds on the half-duplex communication complexity. In SOFSEM 2021: Theory and Practice of Computer Science - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25-29, 2021, Proceedings, volume 12607 of Lecture Notes in Computer Science, pages 233-248. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-67731-2_17.
  2. Irit Dinur and Or Meir. Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity. In Ran Raz, editor, 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume 50 of LIPIcs, pages 3:1-3:51. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.3.
  3. Jeff Edmonds, Russell Impagliazzo, Steven Rudich, and Jirí Sgall. Communication complexity towards lower bounds on circuit depth. Comput. Complex., 10(3):210-246, 2001. URL: https://doi.org/10.1007/s00037-001-8195-x.
  4. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 89-98. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.19.
  5. Anna Gál. A characterization of span program size and improved lower bounds for monotone span programs. Comput. Complex., 10(4):277-296, 2001. URL: https://doi.org/10.1007/s000370100001.
  6. Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson. Toward better formula lower bounds: The composition of a function and a universal relation. SIAM J. Comput., 46(1):114-131, 2017. URL: https://doi.org/10.1137/15M1018319.
  7. Johan Håstad. The shrinkage exponent of de morgan formulas is 2. SIAM J. Comput., 27(1):48-64, 1998. URL: https://doi.org/10.1137/S0097539794261556.
  8. Johan Håstad and Avi Wigderson. Composition of the universal relation. In Jin-Yi Cai, editor, Advances In Computational Complexity Theory, Proceedings of a DIMACS Workshop, New Jersey, USA, December 3-7, 1990, volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 119-134. DIMACS/AMS, 1990. URL: http://dimacs.rutgers.edu/Volumes/Vol13.html, URL: https://doi.org/10.1090/dimacs/013/07.
  9. Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, and Alexander V. Smal. Half-duplex communication complexity. In Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao, editors, 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LIPIcs, pages 10:1-10:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.10.
  10. Artur Ignatiev, Ivan Mihajlin, and Alexander Smal. Super-cubic lower bound for generalized karchmer-wigderson games. Electron. Colloquium Comput. Complex., TR22-016, 2022. URL: https://eccc.weizmann.ac.il/report/2022/016, URL: http://arxiv.org/abs/TR22-016.
  11. Kazuo Iwama and Hiroki Morizumi. An explicit lower bound of 5n - o(n) for boolean circuits. In Krzysztof Diks and Wojciech Rytter, editors, Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings, volume 2420 of Lecture Notes in Computer Science, pages 353-364. Springer, 2002. URL: https://doi.org/10.1007/3-540-45687-2_29.
  12. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-24508-4.
  13. 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.
  14. Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 539-550. ACM, 1988. URL: https://doi.org/10.1145/62212.62265.
  15. Valeriy Mihailovich Khrapchenko. Complexity of the realization of a linear function in the class of II-circuits. Mathematical Notes of the Academy of Sciences of the USSR, 9(1):21-23, 1971. Google Scholar
  16. Valeriy Mihailovich Khrapchenko. On a relation between the complexity and the depth of formula. Methods of Discrete Analysis in Synthesis of Control Systems, 32:76-94, 1978. Google Scholar
  17. Jiatu Li and Tianqi Yang. 3.1n - o(n) circuit lower bounds for explicit functions. Electron. Colloquium Comput. Complex., page 23, 2021. URL: https://eccc.weizmann.ac.il/report/2021/023, URL: http://arxiv.org/abs/TR21-023.
  18. Ivan Mihajlin and Alexander Smal. Toward better depth lower bounds: The XOR-KRW conjecture. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 38:1-38:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.38.
  19. Alexander A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Comb., 10(1):81-93, 1990. URL: https://doi.org/10.1007/BF02122698.
  20. Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. Google Scholar
  21. Bella Abramovna Subbotovskaya. Realization of linear functions by formulas using ∧, ∨, ¬. In Doklady Akademii Nauk, volume 136-3, pages 553-555. Russian Academy of Sciences, 1961. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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