Gap-Hamming problem

Gap-Hamming Problem

In communication complexity, the Gap-Hamming problem roughly states that, if Alice and Bob are each given a string, then any communication protocol Alice and Bob use to compute the Hamming distance between their strings does (asymptotically) no better than Bob sending his whole string to Alice. More specifically, if Alice and Bob are each given $n$-bit strings, there exists no communication protocol that lets Alice compute the hamming distance between their strings to within $n/2\pm {\sqrt {n}}$ using less than $\Omega (n)$ bits.

The Gap-Hamming problem has applications to proving lower bounds for many streaming algorithms, including moment frequency estimation and entropy estimation.

Formal Statement

In this problem, Alice and Bob each receive a string, $x,y\in \{\pm 1\}^{n}$ and Alice is required to compute the function

$\mathrm {GHD} (x,y)={\begin{cases}-1&D_{H}(x,y)\leq {\frac {n}{2}}-{\sqrt {n}}\\+1&D_{H}(x,y)\geq {\frac {n}{2}}+{\sqrt {n}}\\*&{\text{otherwise}}.\end{cases}}$