Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination

DOI10.1007/978-3-540-70575-8_62MaRDI QIDQ3521964zbMATH OpenOpenAlexFDO

Authors Sudipto Guha, Andrew McGregor

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_62

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds for multi-pass processing of multiple data streams
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• Robust lower bounds for communication and stream computation
• Polynomial pass lower bounds for graph streaming algorithms
• Superlinear lower bounds for multipass graph processing

Cited in

(6)

• On the monotonicity of a data stream
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• Superlinear lower bounds for multipass graph processing
• Streaming algorithms for planar convex hulls
• Polynomial pass lower bounds for graph streaming algorithms
• Lower bounds for multi-pass processing of multiple data streams

This page was built for publication: Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination

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