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$.
Categories: cs.CC