Equality is Far Weaker than Constant-Cost Communication
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915390778507264 |
|---|---|
| author | Göös, Mika Harms, Nathaniel Riazanov, Artur |
| author_facet | Göös, Mika Harms, Nathaniel Riazanov, Artur |
| contents | We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{Ω(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, Göös, Harms, and Hatami ( STOC 2025), that constant-cost communication does not reduce to the $k$-Hamming Distance hierarchy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_11162 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Equality is Far Weaker than Constant-Cost Communication Göös, Mika Harms, Nathaniel Riazanov, Artur Computational Complexity We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{Ω(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, Göös, Harms, and Hatami ( STOC 2025), that constant-cost communication does not reduce to the $k$-Hamming Distance hierarchy. |
| title | Equality is Far Weaker than Constant-Cost Communication |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2507.11162 |