Theory of Computing
-------------------
Title     : Robust Lower Bounds for Communication and Stream Computation
Authors   : Amit Chakrabarti, Graham Cormode, and Andrew McGregor
Volume    : 12
Number    : 10
Pages     : 1-35
URL       : https://theoryofcomputing.org/articles/v012a010

Abstract
--------

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. 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 permutations.
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 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.

---------

A short version of this article is available in the Proceedings of
the 40th Annual ACM Symposium on Theory of Computing (STOC'08),
ACM, pp. 641-650.  Compared to the conference presentation,
this version considerably expands the detail of the discussion and
in the proofs, and substantially changes some of the proof
techniques.