2009/02/13 by Joshua Brody, Amit Chakrabarti, Brody, Joshua +1
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #cs.CC #cs.DB #cs.DS
paper · pdf · doi:10.48550/arxiv.0902.2399
arxiv created 2009/02/17 · arxiv updated 2009/12/01
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 + √ n) or small (i.e., at most n/2 - √ n); they do not care if it is neither large nor small. This Θ(√ 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 - Θ(√(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.