Better Gap-Hamming lower bounds via better round elimination

Joshua Brody; Amit Chakrabarti; Oded Regev; Thomas Vidick; Ronald De Wolf

doi:10.1007/978-3-642-15369-3_36

Better Gap-Hamming lower bounds via better round elimination

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald De Wolf

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 ²logk)) 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.

Original language	English (US)
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings
Pages	476-489
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-15369-3_36
State	Published - 2010
Event	13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 - Barcelona, Spain Duration: Sep 1 2010 → Sep 3 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6302 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
Country/Territory	Spain
City	Barcelona
Period	9/1/10 → 9/3/10

Keywords

Communication Complexity
Gap Hamming Distance
Measure Concentration
Round Elimination

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Brody, J., Chakrabarti, A., Regev, O., Vidick, T., & De Wolf, R. (2010). Better Gap-Hamming lower bounds via better round elimination. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings (pp. 476-489). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6302 LNCS). https://doi.org/10.1007/978-3-642-15369-3_36

Better Gap-Hamming lower bounds via better round elimination. / Brody, Joshua; Chakrabarti, Amit; Regev, Oded et al.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. 2010. p. 476-489 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6302 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Brody, J, Chakrabarti, A, Regev, O, Vidick, T & De Wolf, R 2010, Better Gap-Hamming lower bounds via better round elimination. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6302 LNCS, pp. 476-489, 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010, Barcelona, Spain, 9/1/10. https://doi.org/10.1007/978-3-642-15369-3_36

Brody J, Chakrabarti A, Regev O, Vidick T, De Wolf R. Better Gap-Hamming lower bounds via better round elimination. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. 2010. p. 476-489. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-15369-3_36

Brody, Joshua ; Chakrabarti, Amit ; Regev, Oded et al. / 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, Proceedings. 2010. pp. 476-489 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6f1159da48a84c1f9e36836161c74172,

title = "Better Gap-Hamming lower bounds via better round elimination",

abstract = "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.",

keywords = "Communication Complexity, Gap Hamming Distance, Measure Concentration, Round Elimination",

author = "Joshua Brody and Amit Chakrabarti and Oded Regev and Thomas Vidick and {De Wolf}, Ronald",

year = "2010",

doi = "10.1007/978-3-642-15369-3_36",

language = "English (US)",

isbn = "3642153682",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "476--489",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

note = "13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 ; Conference date: 01-09-2010 Through 03-09-2010",

}

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 -

Better Gap-Hamming lower bounds via better round elimination

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this