Tight lower bounds for selection in randomly ordered streams

Amit Chakrabarti, T. S. Jayram, Mihai PatrascuSODA 2008 · OpenReview

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...

Figure