Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Gap-Hamming-Distance:
TR10-140 | 17th September 2010
Amit Chakrabarti, Oded Regev

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

We prove an optimal $\Omega(n)$ lower bound on the randomized
communication complexity of the much-studied
Gap-Hamming-Distance problem. As a consequence, we
obtain essentially optimal multi-pass space lower bounds in the
data stream model for a number of fundamental problems, including
the estimation of frequency moments.

The Gap-Hamming-Distance problem is a ... more >>>

ISSN 1433-8092 | Imprint