Deterministic Communication Complexity of the Hamming Distance

摘要

A proof for bounding the deterministic communication complexity of the Hammingdistance using recently found results regarding the communication complexity of so called sum type functions and the zeros of Krawtchouk polynomials is presented. An attempt to generalize this to the Hamming distance with alphabet size q greater than 2 is made.