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

algorithms with 2-sided errordata stream modellower boundsset disjointness problem

Mathematics Subject Classification ID

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

Cited in

(3)

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

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)