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 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).