2026-07-21T23:53:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22214 2026-04-17T05:52:26Z ddc:004 open_access

Better Boosting of Communication Oracles, or Not Harms, Nathaniel Riazanov, Artur oracles error reduction communication complexity Suppose we have a two-party communication protocol for f which allows the parties to make queries to an oracle computing g; for example, they may query an Equality oracle. To translate this protocol into a randomized protocol, we must replace the oracle with a randomized subroutine for solving g. If q queries are made, the standard technique requires that we boost the error of each subroutine down to O(1/q), leading to communication complexity which grows as q log q. For which oracles g can this naïve boosting technique be improved? We focus on the oracles which can be computed by constant-cost randomized protocols, and show that the naïve boosting strategy can be improved for the Equality oracle but not the 1-Hamming Distance oracle. Two surprising consequences are (1) a new example of a problem where the cost of computing k independent copies grows superlinear in k, drastically simplifying the only previous example due to Blais & Brody (CCC 2019); and (2) a new proof that Equality is not complete for the class of constant-cost randomized communication (Harms, Wild, & Zamaraev, STOC 2022; Hambardzumyan, Hatami, & Hatami, Israel Journal of Mathematics 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathaniel Harms and Artur Riazanov 2024 Is Part Of LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2024.25 urn:nbn:de:0030-drops-222143 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.25 eng https://creativecommons.org/licenses/by/4.0/legalcode