Tight lower bounds for selection in randomly ordered streams
Lists
Only you see this
Abstract
We show that any algorithm computing the median of a stream presented in random order, using polylog(n) space, requires an optimal Ω (log log n) passes, resolving an open question from the seminal paper on streaming by Munro and Paterson, from FOCS 1978.
BibTeX
@inproceedings{chakrabarti2008tight,
author = {Amit Chakrabarti and T. S. Jayram and Mihai Patrascu},
title = {{Tight lower bounds for selection in randomly ordered streams}},
booktitle = {SODA},
year = {2008},
url = {https://openreview.net/forum?id=mdwOYTm56-_},
}Loading related content...