  We prove that the class of communication problems with public-coin randomized
constant-cost protocols, called $BPP^0$, does not contain a complete problem.
In other words, there is no randomized constant-cost problem $Q \in BPP^0$,
such that all other problems $P \in 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.
