Lower bounds for randomized read/write stream algorithms

DOI10.1145/1250790.1250891zbMath1232.68191OpenAlexW2116117986MaRDI QIDQ3549671

Paul Bearne, Atri Rudra, T. S. Jayram

Publication date: 5 January 2009

Published in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1250790.1250891

zbMATH Keywords

lower boundsset disjointness problemdata stream modelalgorithms with 2-sided error

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Randomized algorithms (68W20)

Related Items

Compressed dynamic range majority and minority data structures ⋮ Reversal complexity revisited ⋮ Tradeoff lower lounds for stack machines