Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-100 | 15th July 2025 12:41

Equality is Far Weaker Than Constant-Cost Communication

RSS-Feed




TR25-100
Authors: Mika Göös, Nathaniel Harms, Artur Riazanov
Publication: 20th July 2025 08:08
Downloads: 75
Keywords: 


Abstract:

We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{\Omega(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, Göös, Harms, and Hatami (STOC 2025), that constant-cost communication does not reduce to the $k$-Hamming Distance hierarchy.



ISSN 1433-8092 | Imprint