Robust lower bounds for communication and stream computation
DOI10.4086/TOC.2016.V012A010zbMATH Open1392.68191OpenAlexW2610229967MaRDI QIDQ2830872FDOQ2830872
Authors: Amit Chakrabarti, Graham Cormode, Andrew McGregor 
Publication date: 1 November 2016
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2016.v012a010
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Cites Work
Cited In (10)
- 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
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Better streaming algorithms for the maximum coverage problem
- 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
- Title not available (Why is that?)
- The Simultaneous Communication of Disjointness with Applications to Data Streams
- Towards Optimal Moment Estimation in Streaming and Distributed Models
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)
