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