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 (2009) Better Gap-Hamming Lower Bounds via Better Round Elimination. . (Unpublished)

[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^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 Ω(n), independent of k, by using different techniques.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information: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 the 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
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:03 Oct 2019 20:59

Repository Staff Only: item control page