Constant-Cost Communication is not Reducible to k-Hamming Distance
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918010199998464 |
|---|---|
| author | Fang, Yuting Göös, Mika Harms, Nathaniel Hatami, Pooya |
| author_facet | Fang, Yuting Göös, Mika Harms, Nathaniel Hatami, Pooya |
| contents | Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to $k$-Hamming Distance, that is, solved with a constant number of deterministic queries to some $k$-Hamming Distance oracle. We exhibit the first examples of constant-cost problems which cannot be reduced to $k$-Hamming Distance.
To prove this separation, we relate it to a natural coding-theoretic question. For $f : \{2, 4, 6\} \to \mathbb{N}$, we say an encoding function $E : \{0, 1\}^n \to \{0, 1\}^m$ is an $f$-code if it transforms Hamming distances according to $\mathrm{dist}(E(x), E(y)) = f(\mathrm{dist}(x, y))$ whenever $f$ is defined. We prove that, if there exist $f$-codes for infinitely many $n$, then $f$ must be affine: $f(4) = (f(2) + f(6))/2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_20204 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constant-Cost Communication is not Reducible to k-Hamming Distance Fang, Yuting Göös, Mika Harms, Nathaniel Hatami, Pooya Computational Complexity Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to $k$-Hamming Distance, that is, solved with a constant number of deterministic queries to some $k$-Hamming Distance oracle. We exhibit the first examples of constant-cost problems which cannot be reduced to $k$-Hamming Distance. To prove this separation, we relate it to a natural coding-theoretic question. For $f : \{2, 4, 6\} \to \mathbb{N}$, we say an encoding function $E : \{0, 1\}^n \to \{0, 1\}^m$ is an $f$-code if it transforms Hamming distances according to $\mathrm{dist}(E(x), E(y)) = f(\mathrm{dist}(x, y))$ whenever $f$ is defined. We prove that, if there exist $f$-codes for infinitely many $n$, then $f$ must be affine: $f(4) = (f(2) + f(6))/2$. |
| title | Constant-Cost Communication is not Reducible to k-Hamming Distance |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2407.20204 |