No Complete Problem for Constant-Cost Randomized Communication

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms +1

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…