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 𝑘-Hamming Distance, that is, solved with a constant number of deterministic queries to some 𝑘-Hamming Distance oracle. We exhibit the first examples of constant-cost problems which cannot be reduced to 𝑘-Hamming Distance. To prove this separation,we relate it to a natural coding-theoretic question. For 𝑓 : 2, 4, 6 → N, we say that an encoding function 𝐸 : 0, 1𝑛 → 0, 1𝑚 is an 𝑓 -code if it transforms Hamming distances according to dist(𝐸(𝑥), 𝐸(𝑦)) = 𝑓 (dist(𝑥,𝑦)) whenever 𝑓 is defined. We prove that, if there exist 𝑓 -codes for infinitely many 𝑛, then 𝑓 must be affine: 𝑓 (4) = ( 𝑓 (2) + 𝑓 (6))/2.