Chakrabarti, Amit, Cormode, Graham and McGregor, Andrew (2016) Robust lower bounds for communication and stream computation. Theory of Computing, 12 . pp. 1-35. 10. doi:10.4086/toc.2016.v012a010 ISSN 1557-2862.

PDF WRAP_v012a010.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (694Kb)

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

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Streaming technology (Telecommunications) -- Mathematical models , Streaming audio -- Mathematical models , Streaming video -- Mathematical models
Journal or Publication Title:	Theory of Computing
Publisher:	University of Chicago, Department of Computer Science
ISSN:	1557-2862
Official Date:	28 August 2016
Dates:	Date Event 28 August 2016 Published 22 August 2016 Accepted 28 June 2014 Submitted
Volume:	12
Page Range:	pp. 1-35
Article Number:	10
DOI:	10.4086/toc.2016.v012a010
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access (Creative Commons)
Date of first compliant deposit:	24 August 2016
Date of first compliant Open Access:	24 August 2016
Funder:	National Science Foundation (U.S.) (NSF), Syracuse university. McLane Fellowship, European Research Council (ERC), Yahoo! Research Labs, Royal Society (Great Britain). Wolfson Research Merit Award (RSWRMA), Google (Firm)
Grant number:	CCF-0448277, IIS-0916565, CCF-0953754, CCF-1320719, (NSF), 2014-CoG 647557 (ERC)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads