A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences
| dc.creator | Brody, Joshua | |
| dc.creator | Chakrabarti, Amit | |
| dc.date | 2009-02-13 | |
| dc.date | 2009-02-17 | |
| dc.date.accessioned | 2026-07-07T12:42:04Z | |
| dc.date.available | 2026-07-07T12:42:04Z | |
| dc.description | 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 $Θ(\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 $Ω(n)$ lower bound on this problem was known only in the one-way setting. We prove an $Ω(n)$ lower bound for randomized protocols that use any constant number of rounds. As a consequence we conclude, for instance, that $ε$-approximately counting the number of distinct elements in a data stream requires $Ω(1/ε^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 - Θ(\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 $Ω(n)$ lower bound on the one-way randomized communication complexity. | |
| dc.identifier | https://arxiv.org/abs/0902.2399 | |
| dc.identifier | http://arxiv.org/abs/0902.2399 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/219949 | |
| dc.subject | Computational Complexity | |
| dc.subject | Databases | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences | |
| dc.type | text |