Communication Complexity of Computing the Hamming Distance
King F. Pang, Abbas El Gamal · SIAM Journal on Computing · 1986
Let ${\bf x},{\bf y} \in \{ 0,1\} ^n $. Persons A and B are given ${\bf x}$ and ${\bf y}$ respectively. They communicate in order that both find the Hamming Distance $d_H^n ({\bf x},{\bf y})$. Three communication models, viz, deterministic, $\varepsilon $-error and $\varepsilon $-randomized, are considered. Let $C(d_H^n )$, $C_\varepsilon (d_H^n )$ and $D_\varepsilon (d_H^n )$ be the respective minimum number of bits that must be communicated under the three models. It is shown that \[ n + \log (n + 1 - \sqrt n ) \leqq C\left( {d_H^n } \right) \leqq n + \lceil {\log (n + 1)} \rceil . \] It is also shown that both $C_\varepsilon (d_H^n )$ and $D_\varepsilon (d_H^n )$ are lower bounded by $\Omega (n)$, thus solving an open problem posed by Yao.