Constant-Cost Communication is not Reducible to k-Hamming Distance

Abstract

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$.