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]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
See Usage Policy. 273kB |
|
PDF
- Submitted Version
See Usage Policy. 158kB |
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: |
| ||||||||||||||||||||
| ORCID: |
| ||||||||||||||||||||
| 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: |
| ||||||||||||||||||||
| Subject Keywords: | Communication Complexity; Gap Hamming Distance; Round Elimination; Measure Concentration | ||||||||||||||||||||
| Series Name: | Lecture Notes in Computer Science | ||||||||||||||||||||
| Issue or Number: | 6302 | ||||||||||||||||||||
| DOI: | 10.1007/978-3-642-15369-3_36 | ||||||||||||||||||||
| 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: | 16 Nov 2021 17:02 |
Repository Staff Only: item control page
