Constant-Cost Communication is not Reducible to k-Hamming Distance
<|reference_start|>Constant-Cost Communication is not Reducible to k-Hamming Distance: 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$.<|reference_end|>
@article{fang2024constant-cost,
    title={Constant-Cost Communication is not Reducible to k-Hamming Distance},
    author={Yuting Fang, Mika G"o"os, Nathaniel Harms, Pooya Hatami},
    journal={arXiv preprint arXiv:2407.20204},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.20204},
    primaryClass={cs.CC}
}