Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > JOKERS:
Reports tagged with jokers:
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