AN OPTIMAL LOWER BOUND ON THE COMMUNICATION COMPLEXITY OF GAP-HAMMING-DISTANCE
AN OPTIMAL LOWER BOUND ON THE COMMUNICATION COMPLEXITY OF GAP-HAMMING-DISTANCE
复制标题
DOI：
10.1137/120861072
复制
发表时间：
2012-01-01
影响因子：
1.6
通讯作者：
Regev, Oded
中科院分区：
文献类型：
--
作者：
Chakrabarti, Amit;Regev, Oded
我们证明了一个最佳的Omega（n）下界的随机通信复杂性的研究间隙汉明距离问题。因此，我们获得基本上最佳的多通空间下界的数据流模型的一些基本问题，包括频率矩的估计。间隙汉明距离问题是一个通信问题，其中Alice和Bob分别接收n位字符串x和y。他们承诺x和y之间的汉明距离至少是n/2 + root n或至多是n/2 - root n，他们的目标是决定哪种情况。自从Indyk和Woodruff正式提出这个问题以来[Proceedings of the 44 th Annual IEEE Symposium on Foundations of Computer Science，2003，pp. 283-289]，已经证明使用n比特通信的朴素协议是渐近最优的。证明了该猜想在几种特殊情况下是成立的，如：例如，在一个实施例中，当通信是确定性的或者当通信的回合数有限时。上述结果的证明完全解决了这一猜想，它是基于一个关于高斯空间中相关性的新的几何陈述，与Borell [Z]的结果有关。华什弗鲁Gebiete，70（1985），pp. 1-13]。为了证明这一几何陈述，我们证明了高斯空间中不太小的集合的随机投影接近于平移正态变量的混合。
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 + root n or at most n/2 - root 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 naive 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.