No Complete Problem for Constant-Cost Randomized Communication

Abstract

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called $BP{P}^0$, does not contain a complete problem. In other words, there is no randomized constant-cost problem $Q\in BP{P}^0$, such that all other problems $P\in BP{P}^0$ can be computed by a constant-cost deterministic protocol with access to an oracle for $Q$. We also show that the $k$-Hamming Distance problems form an infinite hierarchy within $BP{P}^0$. Previously, it was known only that Equality is not complete for $BP{P}^0$. We introduce a new technique, using Ramsey theory, that can prove lower bounds against arbitrary oracles in $BP{P}^0$, and more generally, we show that $k$-Hamming Distance matrices cannot be expressed as a Boolean combination of any constant number of matrices which forbid large Greater-Than subproblems.

24 pages