Better Boosting of Communication Oracles, or Not
<|reference_start|>Better Boosting of Communication Oracles, or Not: 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 naive boosting technique be improved?   We focus on the oracles which can be computed by constant-cost randomized protocols, and show that the naive 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).<|reference_end|>
@article{harms2024better,
    title={Better Boosting of Communication Oracles, or Not},
    author={Nathaniel Harms, Artur Riazanov},
    journal={arXiv preprint arXiv:2410.00838},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.00838},
    primaryClass={cs.CC cs.DS}
}