Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Robust lower bounds for communication and stream computation

Tools
- Tools
+ Tools

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.
Official URL: http://dx.doi.org/10.1145/1374376.1374470

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:
DateEvent
17 May 2008Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us