Lower bounds for randomized read/write stream algorithms

DOI10.1145/1250790.1250891MaRDI QIDQ3549671zbMATH OpenOpenAlexFDO

Authors Paul Bearne, T. S. Jayram, Atri Rudra

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

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

Cited in

(3)

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

This page was built for publication: Lower bounds for randomized read/write stream algorithms

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