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 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.

Authors

• Yuting Fang
• Lianna Hambardzumyan
• Nathaniel Harms
• Pooya Hatami

Keywords

• Constant-Cost Communication
• Equality
• Greater-Than
• Hamming Distance
• Randomized Communication
• Stability