Chakrabarti, Amit, Cormode, Graham and McGregor, Andrew (2008) Robust lower bounds for communication and stream computation. In: Fortieth annual ACM symposium on Theory of computing. Published in: Proceedings of the fortieth annual ACM symposium on Theory of computing pp. 641-650. ISBN 9781605580470. doi:10.1145/1374376.1374470

Research output not available from this repository, contact author.

Request Changes to record.

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

Item Type:	Conference Item (Paper)
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Proceedings of the fortieth annual ACM symposium on Theory of computing
Publisher:	ACM
ISBN:	9781605580470
Book Title:	Proceedings of the fourtieth annual ACM symposium on Theory of computing - STOC 08
Official Date:	17 May 2008
Dates:	Date Event 17 May 2008 Published
Page Range:	pp. 641-650
DOI:	10.1145/1374376.1374470
Status:	Peer Reviewed
Publication Status:	Published
Conference Paper Type:	Paper
Title of Event:	Fortieth annual ACM symposium on Theory of computing
Type of Event:	Other

Request changes or add full text files to a record

Repository staff actions (login required)

View Item