Email this article Half-duplex communication complexity with adversary can be less than the classical communication complexity
- Authors: Vereshchagin N.K.1,2, Dektyarev M.V.1
-
Affiliations:
- Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
- Faculty of Computer Science, National Research University Higher School of Economics, Moscow, Russia
- Issue: Vol 216, No 6 (2025)
- Pages: 3-45
- Section: Articles
- URL: https://bakhtiniada.ru/0368-8666/article/view/306711
- DOI: https://doi.org/10.4213/sm10159
- ID: 306711
Cite item
Open Access
Access granted
Subscription Access
Abstract
Half-duplex communication complexity with adversary was defined in [11]. Half-duplex communication protocols generalize classical protocols defined by Yao in [2]. It has been unknown so far whether or not the communication complexities defined by these models are different. We answer this question: we exhibit a function whose half-duplex communication complexity with adversary is strictly less than its classical communication complexity.
About the authors
Nikolai Konstantinovich Vereshchagin
Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia; Faculty of Computer Science, National Research University Higher School of Economics, Moscow, Russia
Email: nikolay.vereshchagin@math.msu.ru; nikolay.vereshchagin@gmail.com
Mikhail Vladimirovich Dektyarev
Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
Email: mikhail.dektiarev@gmail.com
References
- Y. Dementiev, A. Ignatiev, V. Sidelnik, A. Smal, M. Ushakov, “New bounds on the half-duplex communication complexity”, SOFSEM 2021: theory and practice of computer science, Lecture Notes in Comput. Sci., 12607, Springer, Cham, 2021, 233–248
- K. Hoover, R. Impagliazzo, I. Mihajlin, A. V. Smal, “Half-duplex communication complexity”, 29th international symposium on algorithms and computation (ISAAC 2018), LIPIcs. Leibniz Int. Proc. Inform., 123, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2018, 10, 12 pp.
- M. Karchmer, A. Wigderson, “Monotone circuits for connectivity require super-logarithmic depth”, STOC {'}88: Proceedings of the 20th annual ACM symposium on theory of computing (Chicago, IL, 1988), ACM, New York, 1988, 539–550
- A. Ignatiev, I. Mihajlin, A. Smal, “Super-cubic lower bound for generalized Karchmer–Wigderson games”, 33rd international symposium on algorithms and computation (ISAAC 2022), LIPIcs. Leibniz Int. Proc. Inform., 248, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2022, 66, 18 pp.
- Hao Wu, An improved composition theorem of a universal relation and most functions via effective restriction
- O. Meir, “Toward better depth lower bounds: two results on the multiplexor relation”, Comput. Complex., 29:1 (2020), 4, 25 pp.
- O. Meir, Toward better depth lower bounds: a KRW-like theorem for strong composition
- A. Nolin, Communication complexity: large output functions, partition bounds, and quantum nonlocality, Ph.D. thesis, Univ. Paris, 2020, 140 pp.
- E. Kushilevitz, N. Nisan, Communication complexity, Reprint of 1997 original, Cambridge Univ. Press, Cambridge, 2006, xiv+189 pp.
- А. В. Смаль, Доказательство нижних оценок на размер формул для булевых функций методами коммуникационной сложности, Дисс. … канд. физ.-матем. наук, ПОМИ РАН, СПб., 2022, 114 с.
- A. C.-C. Yao, “Some complexity questions related to distributive computing (Preliminary report)”, STOC{'}79: Proceedings of the eleventh annual ACM symposium on theory of computing (Atlanta, GA, 1979), ACM, New York, 1979, 209–213
Supplementary files
