Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HALF-DUPLEX COMMUNICATION COMPLEXITY:
Reports tagged with half-duplex communication complexity:
TR20-116 | 1st August 2020
Ivan Mihajlin, Alexander Smal

Toward better depth lower bounds: the XOR-KRW conjecture

Revisions: 2

In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply $\mathbf{P} \not\subseteq \mathbf{NC}^1$ if proven. We also present a weaker version of this conjecture that might be used for breaking $n^3$ lower ... more >>>


TR20-117 | 4th August 2020
Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov

New bounds on the half-duplex communication complexity

Revisions: 3

In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. ... more >>>


TR22-016 | 15th February 2022
Artur Ignatiev, Ivan Mihajlin, Alexander Smal

Super-cubic lower bound for generalized Karchmer-Wigderson games

Revisions: 1

In this paper, we prove a super-cubic lower bound on the size of a communication protocol for generalized Karchmer-Wigderson game for some explicit function $f: \{0,1\}^n\to \{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. ... more >>>


TR23-011 | 13th February 2023
Mikhail Dektiarev, Nikolay Vereshchagin

Half-duplex communication complexity with adversary? can be less than the classical communication complexity

Revisions: 1

Half-duplex communication complexity with adversary was defined in [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Half-duplex communication protocols generalize classical protocols defined by Andrew Yao in [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. It has been ... more >>>




ISSN 1433-8092 | Imprint