Lower bounds for randomized read/write stream algorithms

DOI10.1145/1250790.1250891zbMATH Open1232.68191OpenAlexW2116117986MaRDI QIDQ3549671FDOQ3549671

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)