Robust lower bounds for communication and stream computation

DOI10.4086/TOC.2016.V012A010MaRDI QIDQ2830872zbMATH OpenOpenAlexFDO

Authors Amit Chakrabarti, Graham Cormode, Andrew McGregor

Publication date 1 November 2016

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2016.v012a010

zbMATH Keywords

lower boundsdata streamscommunication complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• An information statistics approach to data stream and communication complexity
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• Tight bounds for distributed functional monitoring

Cites work

• scientific article; zbMATH DE number 2019620 (Why is no real title available?)
• Optimal approximations of the frequency moments of data streams
• Optimal space lower bounds for all frequency moments

Cited in

(10)

• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
• Better streaming algorithms for the maximum coverage problem
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• scientific article; zbMATH DE number 6829278 (Why is no real title available?)
• The Simultaneous Communication of Disjointness with Applications to Data Streams

This page was built for publication: Robust lower bounds for communication and stream computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830872)