Aarhus University Seal

New Unconditional Hardness Results for Dynamic and Online Problems

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Data summarization is an effective approach to dealing with the 'big data' problem. While data summarization problems traditionally have been studied is the streaming model, the focus is starting to shift to distributed models, as distributed/parallel computation seems to be the only viable way to handle today's massive data sets. In this paper, we study ε-approximations, a classical data summary that, intuitively speaking, preserves approximately the density of the underlying data set over a certain range space. We consider the problem of computing ε-approximations for a data set which is held jointly by k players, and give general communication upper and lower bounds that hold for any range space whose discrepancy is known.

Original languageEnglish
Title of host publication56th IEEE Symposium on Foundations of Computer Science (FOCS) Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Number of pages20
PublisherIEEE Computer Society Press
Publication year2015
Publication statusPublished - 2015
EventIEEE Symposium on Foundations of Computer Science - Berkeley, United States
Duration: 18 Oct 201520 Oct 2015
Conference number: 56


ConferenceIEEE Symposium on Foundations of Computer Science
LandUnited States

    Research areas

  • communication complexity, discrepancy, distributed data, ε-approximations

See relations at Aarhus University Citationformats

ID: 87497673