Gap-Hamming problem

In communication complexity, the gap-Hamming problem asks, if Alice and Bob are each given a string, what is the minimal number of bits that they need to exchange in order for Alice to approximately compute the Hamming distance between their strings. The solution to the problem roughly states that, if Alice and Bob are each given a string, then any communication protocol used to compute the Hamming distance between their strings does no better than Bob sending his whole string to Alice. More specifically, if Alice and Bob are each given -bit strings, there exists no communication protocol that lets Alice compute the hamming distance between their strings to within using less than 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, and, respectively, while Alice is required to compute the function,
using the least amount of communication possible. Here, indicates that Alice can return either of and is the Hamming distance between and. 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 requires at least communication. In particular, it requires communication even when and are chosen uniformly at random from.

History

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 and conjectured a linear lower bound in the general case. The question of the infinite-round case 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. 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 and later by Sherstov, and, recently, with an information-theoretic approach by Hadar, Liu, Polyanskiy, and Shayevitz.