gap-Hamming problem

In communication complexity, the gap-Hamming problem asks, if Alice and Bob are each given a (potentially different) 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 (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 $\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{{Cite book |doi=10.1145/1060590.1060621|isbn=9781581139600|chapter=Optimal approximations of the frequency moments of data streams|title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05|pages=202|year=2005|last1=Indyk|first1=Piotr|last2=Woodruff|first2=David|s2cid=7911758}} and entropy estimation.{{Cite journal|last1=Chakrabarti|first1=Amit|last2=Cormode|first2=Graham|last3=Mcgregor|first3=Andrew|date=2010|title=A Near-optimal Algorithm for Estimating the Entropy of a Stream|journal= ACM Transactions on Algorithms|volume=6|issue=3|pages=1–21|doi=10.1145/1798596.1798604|issn=1549-6325|citeseerx=10.1.1.190.5419|s2cid=6733816}}

Formal statement

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

: $\operatorname{GHD}(x, y) = \begin{cases}
+1 & D_H(x, y) \ge \frac{n}{2} + \sqrt{n}\\
-1 & D_H(x, y) \le \frac{n}{2} - \sqrt{n}\\$

& \text{otherwise},

\end{cases}

using the least amount of communication possible. Here, $*$ indicates that Alice can return either of $\pm 1$ and $D_H(x, y)$ is the Hamming distance between $x$ and $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 $\operatorname{GHD}$ requires at least $\Omega(n)$ communication. In particular, it requires $\Omega(n)$ communication even when $x$ and $y$ are chosen uniformly at random from $\{\pm 1\}^n$ .

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 (where Alice is only allowed to receive data from Bob) and conjectured a linear lower bound in the general case.{{Cite book |doi=10.1109/SFCS.2003.1238202|isbn=9780769520407|chapter=Tight lower bounds for the distinct elements problem|title=44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings|pages=283–288|year=2003|last1=Indyk|first1=P.|last2=Woodruff|first2=D.|s2cid=7648045}} 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.{{Cite book |doi=10.1145/1993636.1993644|isbn=9781450306911|arxiv=1009.3460|chapter=An optimal lower bound on the communication complexity of gap-hamming-distance|title=Proceedings of the 43rd annual ACM symposium on Theory of computing - STOC '11|pages=51|year=2011|last1=Chakrabarti|first1=Amit|last2=Regev|first2=Oded|s2cid=10274326}} 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{{Cite journal|last=Vidick|first=Thomas|date=2012|title=A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the gap-Hamming-Distance problem|journal=Chicago Journal of Theoretical Computer Science|volume=18|pages=1–12|doi=10.4086/cjtcs.2012.001|doi-access=free}} and later by Sherstov,{{Cite journal|last=Sherstov|first=Alexander A.|date=2012-05-17|title=The Communication Complexity of Gap Hamming Distance|journal=Theory of Computing|language=EN|volume=8|issue=1|pages=197–208|doi=10.4086/toc.2012.v008a008|issn=1557-2862|doi-access=free}} and, recently, with an information-theoretic approach by Hadar, Liu, Polyanskiy, and Shayevitz.{{Cite arXiv|last1=Shayevitz|first1=Ofer|last2=Polyanskiy|first2=Yury|last3=Liu|first3=Jingbo|last4=Hadar|first4=Uri|date=2019-01-25|title=Communication Complexity of Estimating Correlations|language=en|eprint=1901.09100v2|class=cs.IT}}

References

Category:Computational complexity theory

Category:Quantum complexity theory

Category:Communication