Better Gap-Hamming Lower Bounds via Better Round Elimination

Details Better Gap-Hamming Lower Bounds via Better Round Elimination Better Gap-Hamming Lower Bounds via Better Round Elimination

2009-12-30

arxiv.org/abs/0912.5276v1

Computer Science

Computational Complexity

Scientific paper

Gap Hamming Distance is a well-studied problem in communication complexity, in which Alice and Bob have to decide whether the Hamming distance between their respective n-bit inputs is less than n/2-sqrt(n) or greater than n/2+sqrt(n). We show that every k-round bounded-error communication protocol for this problem sends a message of at least Omega(n/(k^2\log k)) bits. This lower bound has an exponentially better dependence on the number of rounds than the previous best bound, due to Brody and Chakrabarti. Our communication lower bound implies strong space lower bounds on algorithms for a number of data stream computations, such as approximating the number of distinct elements in a stream. Subsequent to this result, the bound has been improved by some of us to the optimal Omega(n), independent of k, by using different techniques.

Affiliated with

Also associated with

No associations

Rating

Better Gap-Hamming Lower Bounds via Better Round Elimination does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Better Gap-Hamming Lower Bounds via Better Round Elimination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Better Gap-Hamming Lower Bounds via Better Round Elimination will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-33714