๐ฎ
๐ฎ
The Ethereal
Half-duplex communication complexity with adversary can be less than the classical communication complexity
May 27, 2024 ยท The Ethereal ยท ๐ Electron. Colloquium Comput. Complex.
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Mikhail Dektiarev, Nikolay Vereshchagin
arXiv ID
2405.16881
Category
cs.CC: Computational Complexity
Cross-listed
cs.IT
Citations
0
Venue
Electron. Colloquium Comput. Complex.
Last Checked
3 months ago
Abstract
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 unknown so far whether the communication complexities defined by these models are different or not. In the present paper we answer this question: we exhibit a function whose half-duplex communication complexity with adversary is strictly less than its classical communication complexity.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Computational Complexity
๐ฎ
๐ฎ
The Ethereal
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
๐ฎ
๐ฎ
The Ethereal
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
๐ฎ
๐ฎ
The Ethereal
The Hardness of Approximation of Euclidean k-means
๐ฎ
๐ฎ
The Ethereal
Slightly Superexponential Parameterized Problems
๐ฎ
๐ฎ
The Ethereal