No Complete Problem for Constant-Cost Randomized Communication
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911821107036160 |
|---|---|
| author | Fang, Yuting Hambardzumyan, Lianna Harms, Nathaniel Hatami, Pooya |
| author_facet | Fang, Yuting Hambardzumyan, Lianna Harms, Nathaniel Hatami, Pooya |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_00812 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | No Complete Problem for Constant-Cost Randomized Communication Fang, Yuting Hambardzumyan, Lianna Harms, Nathaniel Hatami, Pooya Computational Complexity 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. |
| title | No Complete Problem for Constant-Cost Randomized Communication |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.00812 |