TR09-015 Authors: Joshua Brody, Amit Chakrabarti

Publication: 3rd March 2009 17:49

Downloads: 3229

Keywords:

The Gap-Hamming-Distance problem arose in the context of proving space

lower bounds for a number of key problems in the data stream model. In

this problem, Alice and Bob have to decide whether the Hamming distance

between their $n$-bit input strings is large (i.e., at least $n/2 +

\sqrt n$) or small (i.e., at most $n/2 - \sqrt n$); they do not care if

it is neither large nor small. This $\Theta(\sqrt n)$ gap in the problem

specification is crucial for capturing the approximation allowed to a

data stream algorithm.

Thus far, for randomized communication, an $\Omega(n)$ lower bound on

this problem was known only in the one-way setting. We prove an

$\Omega(n)$ lower bound for randomized protocols that use any constant

number of rounds.

As a consequence we conclude, for instance, that $\epsilon$-approximately

counting the number of distinct elements in a data stream requires

$\Omega(1/\epsilon^2)$ space, even with multiple (a constant number of)

passes over the input stream. This extends earlier one-pass lower

bounds, answering a long-standing open question. We obtain similar

results for approximating the frequency moments and for approximating

the empirical entropy of a data stream.

In the process, we also obtain tight $n - \Theta(\sqrt{n}\log n)$ lower

and upper bounds on the one-way deterministic communication complexity

of the problem. Finally, we give a simple combinatorial proof of an

$\Omega(n)$ lower bound on the one-way randomized communication

complexity.