CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20190320-105826650

[img] PDF - Published Version
See Usage Policy.

267Kb
[img] PDF - Submitted Version
See Usage Policy.

154Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190320-105826650

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/978-3-642-15369-3_36DOIArticle
https://rdcu.be/b5WovPublisherFree ReadCube access
https://arxiv.org/abs/0912.5276arXivDiscussion Paper
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFCCF-0448277
NSFIIS-0916565
McLane Family FellowshipUNSPECIFIED
Israel Science FoundationUNSPECIFIED
European Research Council (ERC)015848
Wolfson Family Charitable TrustUNSPECIFIED
Army Research Office (ARO)W911NF-09-1-0440
NSFCCF-0905626
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:https://resolver.caltech.edu/CaltechAUTHORS:20190320-105826650
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93990
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:20 Mar 2019 18:17
Last Modified:29 Jul 2020 16:24

Repository Staff Only: item control page