An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

Amit Chakrabarti 1 Oded Regev 2
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We prove an optimal $\Omega(n)$ lower bound on the randomized communication complexity of the much-studied gap-hamming-distance problem. As a consequence, we obtain essentially optimal multipass space lower bounds in the data stream model for a number of fundamental problems, including the estimation of frequency moments. The gap-hamming-distance problem is a communication problem, wherein Alice and Bob receive $n$-bit strings $x$ and $y$, respectively. They are promised that the Hamming distance between $x$ and $y$ is either at least $n/2+\sqrt{n}$ or at most $n/2-\sqrt{n}$, and their goal is to decide which of these is the case. Since the formal presentation of the problem by Indyk and Woodruff [Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 283--289], it had been conjectured that the naïve protocol, which uses $n$ bits of communication, is asymptotically optimal. The conjecture was shown to be true in several special cases, e.g., when the communication is deterministic or when the number of rounds of communication is limited. The proof of our aforementioned result, which settles this conjecture fully, is based on a new geometric statement regarding correlations in Gaussian space, related to a result of Borell [Z. Wahrsch. Verw. Gebiete, 70 (1985), pp. 1--13]. To prove this geometric statement, we show that random projections of not-too-small sets in Gaussian space are close to a mixture of translated normal variables.
Type de document :
Article dans une revue
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2012, 41 (5), pp.1299-1317. 〈10.1137/120861072〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01111554
Contributeur : Brigitte Briot <>
Soumis le : vendredi 30 janvier 2015 - 15:25:19
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Collections

Citation

Amit Chakrabarti, Oded Regev. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance . SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2012, 41 (5), pp.1299-1317. 〈10.1137/120861072〉. 〈hal-01111554〉

Partager

Métriques

Consultations de la notice

121