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

DOI10.1007/978-3-540-70575-8_62zbMath1153.68381OpenAlexW1580721607MaRDI QIDQ3521964

Andrew McGregor, Sudipto Guha

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)

Related Items (4)

Superlinear lower bounds for multipass graph processing ⋮ On the monotonicity of a data stream ⋮ Unnamed Item ⋮ Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy

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