No Complete Problem for Constant-Cost Randomized Communication

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called BPP0, does not contain a complete problem. In other words, there is no randomized constant-cost problem Q ∈ BPP0, such that all other problems P ∈ BPP0 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 BPP0. Previously, it was known only that Equality is not complete for BPP0. We introduce a new technique, using Ramsey theory, that can prove lower bounds against arbitrary oracles in BPP0, 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.