Gap-Hamming problem

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

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

using the least amount of communication possible. Here, ${\displaystyle *}$ indicates that Alice can return either of ${\displaystyle \pm 1}$ and ${\displaystyle D_{H}(x,y)}$ is the Hamming distance between ${\displaystyle x}$ and ${\displaystyle y}$. In other words, Alice needs to return whether Bob's string is significantly similar or significantly different from hers while minimizing the number of bits she exchanges with Bob.

The problem's solution states that computing ${\displaystyle \operatorname {GHD} }$ requires at least ${\displaystyle \Omega (n)}$ communication. In particular, it requires ${\displaystyle \Omega (n)}$ communication even when ${\displaystyle x}$ and ${\displaystyle y}$ are chosen uniformly at random from ${\displaystyle \{\pm 1\}^{n}}$.

The gap-Hamming problem was originally proposed by Indyk and Woodruff in the early 2000's, who initially proved a linear lower bound on the one-way communication complexity of the problem (where Alice is only allowed to receive data from Bob) and conjectured a linear lower bound in the general case.[3] The question of the infinite-round case (in which Alice and Bob are allowed to exchange as many messages as desired) remained open until Chakrabarti and Regev proved, via an anti-concentration argument, that the general problem also has linear lower bound complexity, thus settling the original question completely.[4] This result was followed by a series of other papers that sought to simplify or find new approaches to proving the desired lower bound, notably first by Vidick[5] and later by Sherstov,[6] and, recently, with an information-theoretic approach by Hadar, Liu, Polyanskiy, and Shayevitz.[7]