2026-07-23T19:43:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24424 2026-04-13T09:38:56Z ddc:004 open_access

Equality Is Far Weaker Than Constant-Cost Communication Göös, Mika Harms, Nathaniel Riazanov, Artur Equality oracle constant-cost communication gamma-2 norm spectral norm We exhibit an n-bit communication problem with a constant-cost randomized protocol but which requires n^Ω(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Göös and Nathaniel Harms and Artur Riazanov 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.58 urn:nbn:de:0030-drops-244246 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.58 eng https://creativecommons.org/licenses/by/4.0/legalcode