تقرير
No Complete Problem for Constant-Cost Randomized Communication
| العنوان: | No Complete Problem for Constant-Cost Randomized Communication |
|---|---|
| المؤلفون: | Fang, Yuting, Hambardzumyan, Lianna, Harms, Nathaniel, Hatami, Pooya |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - 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. Comment: 24 pages |
| نوع الوثيقة: | Working Paper |
| الوصول الحر: | http://arxiv.org/abs/2404.00812Test |
| رقم الانضمام: | edsarx.2404.00812 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |