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\ → N, we say an encoding function E : \0, 1\ⁿ → \0, 1\ᵐ is an f-code if it transforms Hamming distances according to dist(E(x), E(y)) = f(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$.