No Complete Problem for Constant-Cost Randomized Communication

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