Name
Abstract | ||
|---|---|---|
We prove that any oblivious algorithm using space S to find the median of a list of n integers from {1, ..., 2n} requires time Omega(n log log(S) n). This bound also applies to the problem of determining whether the median is odd or even. It is nearly optimal since Chan, following Munro and Raman, has shown that there is a (randomized) selection algorithm using only s registers, each of which can store an input value or O(log n)-bit counter, that makes only O(log logs n) passes over the input. The bound also implies a size lower bound for read-once branching programs computing the low order bit of the median and implies the analog of P not equal NP boolean AND coNP for length o(n log log n) oblivious branching programs. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-47672-7_9 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Integer,Binary logarithm,Discrete mathematics,Combinatorics,Upper and lower bounds,Shell element,Mathematics,Branching (version control),Bounded function | Journal | 9134 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.35 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Vincent Liew | 2 | 7 | 1.16 |
| Mihai Patrascu | 3 | 1153 | 49.84 |