Equality is Far Weaker than Constant-Cost Communication
By: Mika Göös, Nathaniel Harms, Artur Riazanov
Potential Business Impact:
Makes computers solve problems faster without guessing.
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\"o\"os, Harms, and Hatami ( STOC 2025), that constant-cost communication does not reduce to the $k$-Hamming Distance hierarchy.
Similar Papers
Sign-Rank of $k$-Hamming Distance is Constant
Computational Complexity
Makes computer math problems easier to solve.
Lower Bounds on Relative Error Quantum Compression and Classical Shadows
Quantum Physics
Connects two computer problems to save information.
Pseudodeterministic Communication Complexity
Computational Complexity
Makes computers solve problems much faster.