Paper Info
Title
Tight lower bounds for selection in randomly ordered streams
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.
Year
DOI
Venue
2008
10.5555/1347082.1347161
SODA
Keywords
Field
DocType
log log n,seminal paper,open question,random order,lower bound
Log-log plot,Discrete mathematics,Combinatorics,STREAMS,Mathematics
Conference
ISBN
Citations 
PageRank 
978-0-89871-698-6
27
1.14
References 
Authors
17
3
Name
Order
Citations
PageRank
Amit Chakrabarti171438.18
T. S. Jayram2137375.87
Mihai Patrascu3115349.84