A Caltech Library Service

Better Gap-Hamming Lower Bounds via Better Round Elimination

Brody, Joshua and Chakrabarti, Amit and Regev, Oded and Vidick, Thomas and de Wolf, Ronald (2010) Better Gap-Hamming Lower Bounds via Better Round Elimination. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. No.6302. Springer , Berlin, pp. 476-489. ISBN 978-3-642-15368-6.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2010 Springer-Verlag Berlin Heidelberg. Supported in part by NSF Grant CCF-0448277. Part of this work was done while the author was visiting CWI and Tel Aviv University. Supported in part by NSF Grants CCF-0448277 and IIS-0916565 and a McLane Family Fellowship. Supported by the Israel Science Foundation, by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848, by the Wolfson Family Charitable Trust, and by a European Research Council (ERC) Starting Grant. Supported by ARO Grant W911NF-09-1-0440 and NSF Grant CCF-0905626. Part of this work was done while the author was visiting CWI and Tel Aviv University. Supported by a Vidi grant from Netherlands Organization for Scientific Research (NWO). We thank Ishay Haviv for discussions during the early stages of this work.
Funding AgencyGrant Number
McLane Family FellowshipUNSPECIFIED
Israel Science FoundationUNSPECIFIED
European Research Council (ERC)015848
Wolfson Family Charitable TrustUNSPECIFIED
Army Research Office (ARO)W911NF-09-1-0440
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)UNSPECIFIED
Subject Keywords:Communication Complexity; Gap Hamming Distance; Round Elimination; Measure Concentration
Series Name:Lecture Notes in Computer Science
Issue or Number:6302
Record Number:CaltechAUTHORS:20190320-105826650
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93990
Deposited By: Tony Diaz
Deposited On:20 Mar 2019 18:17
Last Modified:16 Nov 2021 17:02

Repository Staff Only: item control page