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²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.
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.Attached Files
Published - Brody2010_Chapter_BetterGap-HammingLowerBoundsVi.pdf
Submitted - 0912.5276.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:b5dfe4a123ec6c89b8b661d88df17208
|
273.8 kB | Preview Download |
|
md5:240a5bfe386f0aaddffb6f2834d65764
|
158.4 kB | Preview Download |
Additional details
- Eprint ID
- 93990
- Resolver ID
- CaltechAUTHORS:20190320-105826650
- NSF
- CCF-0448277
- NSF
- IIS-0916565
- McLane Family Fellowship
- Israel Science Foundation
- European Research Council (ERC)
- 015848
- Wolfson Family Charitable Trust
- Army Research Office (ARO)
- W911NF-09-1-0440
- NSF
- CCF-0905626
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)
- Created
-
2019-03-20Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
- Series Name
- Lecture Notes in Computer Science
- Series Volume or Issue Number
- 6302