No Complete Problem for Constant-Cost Randomized Communication

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