Constant-Cost Communication Is Not Reducible to k-Hamming Distance
Yuting Fang, Mika GΓΆΓΆs, Nathaniel Harms, Pooya Hatami Β· 2025
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.