Constant-Cost Communication is not Reducible to k-Hamming Distance

Yuting Fang, Mika Göös, Nathaniel Harms +1

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 con…