Better Gap-Hamming lower bounds via better round elimination
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. © 2010 Springer-Verlag.
Cite this item
Brody, J., Chakrabarti, A., Regev, O., Vidick, T., & De Wolf, R. (2010). Better Gap-Hamming lower bounds via better round elimination. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 6302 LNCS, 476–489. https://doi.org/10.1007/978-3-642-15369-3_36
Click Copy to copy the citation, or select the text manually.
2-s2.0-78149311850
Department of Computer Science
Department of Computer Science
Tel Aviv University
University of California, Berkeley
Centrum Wiskunde & Informatica
2010
978-3-642-15368-6
978-3-642-15369-3
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 6302 LNCS
0302-9743
1611-3349
476
489
REVIEWED
OTHER
| Event name | Event acronym | Event place | Event date |
APPROX 2010 | Barcelona, Spain | 2010-09-01 - 2010-09-03 | |