Document Open Access Logo

Toward Better Depth Lower Bounds: The XOR-KRW Conjecture

Authors Ivan Mihajlin, Alexander Smal

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2021.38.pdf
  • Filesize: 0.85 MB
  • 24 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • communication complexity
  • KRW conjecture
  • circuit complexity
  • half-duplex communication complexity
  • Karchmer-Wigderson games
  • multiplexer relation
  • universal relation

Metrics

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

Abstract

In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [Mauricio Karchmer et al., 1995]. This relaxation is still strong enough to imply 𝐏 ̸ ⊆ NC¹ if proven. We also present a weaker version of this conjecture that might be used for breaking n³ lower bound for De Morgan formulas. Our study of this conjecture allows us to partially answer an open question stated in [Dmitry Gavinsky et al., 2017] regarding the composition of the universal relation with a function. To be more precise, we prove that there exists a function g such that the composition of the universal relation with g is significantly harder than just a universal relation. The fact that we can only prove the existence of g is an inherent feature of our approach.
The paper’s main technical contribution is a new approach to lower bounds for multiplexer-type relations based on the non-deterministic hardness of non-equality and a new method of converting lower bounds for multiplexer-type relations into lower bounds against some function. In order to do this, we develop techniques to lower bound communication complexity in half-duplex and partially half-duplex communication models.

Cite As Get BibTex

Ivan Mihajlin and Alexander Smal. Toward Better Depth Lower Bounds: The XOR-KRW Conjecture. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 38:1-38:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CCC.2021.38

Author Details

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

Acknowledgements

We would like to thank the anonymous reviewers who have done a tremendous job carefully reading our paper and whose detailed comments helped us significantly improve the text of the paper and make it more readable.

References

  1. Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, and Robert Robere. KRW composition theorems via lifting. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 43-49. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00013.
  2. 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.
  3. Irit Dinur and Or Meir. Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity. Comput. Complex., 27(3):375-462, 2018. URL: https://doi.org/10.1007/s00037-017-0159-x.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, and Alexander Smal. Half-duplex communication complexity. Electronic Colloquium on Computational Complexity (ECCC), 25:89, 2018. URL: https://eccc.weizmann.ac.il/report/2018/089.
  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. 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. 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.
  12. 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
  13. Sajin Koroth and Or Meir. Improved Composition Theorems for Functions and Relations. In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1-48:18, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.48.
  14. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  15. Or Meir. Toward better depth lower bounds: Two results on the multiplexor relation. Comput. Complex., 29(1):4, 2020. URL: https://doi.org/10.1007/s00037-020-00194-8.
  16. Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. Google Scholar
  17. 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
  18. Avishay Tal. Shrinkage of de morgan formulae by spectral techniques. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 551-560. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.65.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact