Robust lower bounds for communication and stream computation
Robust lower bounds for communication and stream computation
复制标题
通信和流计算的稳健下限
DOI：
10.1145/1374376.1374470
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Mcgregor
中科院分区：
文献类型：
--
作者：
Amit Chakrabarti;Graham Cormode;A. Mcgregor
当在两个或多个播放器之间随机分配输入数据（根据某些已知分布）时，我们研究了评估功能的沟通复杂性，并且可能与信息重叠。这自然扩展了先前研究的可变分区模型，例如最佳案例和最差的分区模型[32,29]。我们旨在了解沟通问题的硬度几乎是对意见分配的几乎所有分配，而不是仅仅持有一些非典型分区。关键应用程序是对经过深入研究的数据流模型。数据流模型中我们的通信下限和下限之间存在很强的联系，这些连接与数据的排序“稳健”。也就是说，我们证明了何时从所有置入率组中选择流中的项目的顺序不是在对手而不是统一（或几乎均匀）的情况下。这种随机数据流模型引起了最近的兴趣，因为这里的下限为流媒体问题的固有硬度提供了更大的证据。我们的结果包括第一个随机分区通信的下限，包括多方集合脱节和间隙 - 束缚距离。两者都很紧。我们还扩展并改善了与选择问题有关的指针跳跃形式（尤其是中位数发现）的形式。总的来说，这些结果在随机数据流模型中产生了各种问题的下限，包括估计不同元素的数量，近似频率矩和分位数估计。
We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models [32,29]. We aim to understand whether the hardness of a communication problem holds for almost every allocation of the input, as opposed to holding for perhaps just a few atypical partitions. A key application is to the heavily studied data stream model. There is a strong connection between our communication lower bounds and lower bounds in the data stream model that are "robust" to the ordering of the data. That is, we prove lower bounds for when the order of the items in the stream is chosen not adversarially but rather uniformly (or near-uniformly) from the set of all permuations. This random-order data stream model has attracted recent interest, since lower bounds here give stronger evidence for the inherent hardness of streaming problems. Our results include the first random-partition communication lower bounds for problems including multi-party set disjointness and gap-Hamming-distance. Both are tight. We also extend and improve previous results [19,7] for a form of pointer jumping that is relevant to the problem of selection (in particular, median finding). Collectively, these results yield lower bounds for a variety of problems in the random-order data stream model, including estimating the number of distinct elements, approximating frequency moments, and quantile estimation.