TY - GEN

T1 - Better Gap-Hamming lower bounds via better round elimination

AU - Brody, Joshua

AU - Chakrabarti, Amit

AU - Regev, Oded

AU - Vidick, Thomas

AU - De Wolf, Ronald

PY - 2010

Y1 - 2010

N2 - 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 - √n or greater than n/2 + √n. We show that every k-round bounded-error communication protocol for this problem sends a message of at least Ω(n/(k 2logk)) 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.

AB - 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 - √n or greater than n/2 + √n. We show that every k-round bounded-error communication protocol for this problem sends a message of at least Ω(n/(k 2logk)) 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.

KW - Communication Complexity

KW - Gap Hamming Distance

KW - Measure Concentration

KW - Round Elimination

UR - http://www.scopus.com/inward/record.url?scp=78149311850&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78149311850&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15369-3_36

DO - 10.1007/978-3-642-15369-3_36

M3 - Conference contribution

AN - SCOPUS:78149311850

SN - 3642153682

SN - 9783642153686

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 476

EP - 489

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010

Y2 - 1 September 2010 through 3 September 2010

ER -