In this paper we study the communication complexity of evaluating functions when the input data is distributed (according to some known distribution) to two or more players. This naturally extends previous models such as the best-case and worst-case partition models to a model that captures random partitions and distributions with redundancy where bits of data may be known to more than one player. This allows us to distinguish functions which require significant communication for almost every allocation of input from those for which only a few cases are hard.There is also a strong connection to proving lower-bounds in the data stream model that are “robust” to the ordering of the data. That is, we prove lower-bounds for when order of the data-stream is not chosen adversarially but rather is determined uniformly (or near-uniformly) from the set of all permuations. This streaming model has attracted recent interest, since lower bounds here give stronger evidence for the inherent hardness of streaming problems.
Our results include the first average-partition communication lower-bounds for problems including multi-party set-disjointness and gap-hamming. Both are tight. We also improve extend and improve previous results for a form of pointer-jumping that is relevant to the problem of selection. 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.
This file was generated by bibtex2html 1.92.