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 n → 0, 1 m 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.

Theorem 1 (Main result). The problem HD 4,4 does not admit a constant-cost deterministic oracleprotocol with query access to HD k , for any constant k.

Why 4, 4? What is so special about using 4, 4 as the multiset of distances of the two unequal rows? Consider the similar problem HD 2,2 defined on matrices x, y ∈ 0, 1 n×n where the answer should be 1 iff there are exactly 2 unequal rows, each with distance 2. Unlike HD 4,4 , this problem can be solved by a 4-Hamming Distance oracle protocol, Protocol 2. To find a deeper explanation for why HD 2,2 reduces to HD k , while HD 4,4 does not, we study in the next section the types of Hamming distance encodings E( • ) that can be used in Step 3 of this protocol.

Oracle-protocol for HD 2,2 on input (x, y):

1. The players verify that there are precisely two unequal rows, as in Step 1 of Protocol 1.

2. The players verify that total Hamming distance is dist(x, y) = 4 using a HD 4 oracle. The players now know the multiset of distances of the two unequal rows is one of 1, 3, 2, 2.

3. It remains to distinguish the above two cases. Let E : 0, 1 n → 0, 1 be the parity code, where E(z) is the parity of z. The players query an Equality oracle * to check if

These strings are equal iff dist(x i , y i ) is even for every row i ∈ [n], meaning that the distances must be 2, 2.

• Note that an Equality oracle can be simulated by one query to any HD k oracle, by padding the input.