Optimal parallel selection has complexity O(log log N) (Q1118404)

It is shown that in the deterministic comparison model for parallel computation, \(p=n\) processors can select the k-th smallest item from a set of n numbers in O(log log n) parallel time. With this result all comprison tasks (selection, merging, sorting) now have upper and lower bounds of the same order in both random and deterministic models. This optimal time bound holds even if \(p=o(n).\) The algorithm is based on the following combinatorial result concerning expander graphs. A graph \(G=(V,E)\) is a weak (A,\(\alpha)\)-expander \((\alpha A<1)\) if, for all \(T\subseteq V\) with \(| T| \geq \alpha \cdot | V|\), \(| N(T)| \geq A\alpha | V|\); here N(T) is the set of neighbors of vertices in T. For T,U\(\subseteq V\), G is an (A,\(\alpha)\)-expander from \(T\to U\) if for all \(X\subseteq T\) with \(| X| \leq \alpha \cdot | U|\), \(| N(X)\cap U| \geq A\cdot | U|\). Expander lemma: Let \(A>B>1\) and \(\alpha\), \(\beta\) be given, \(\alpha A<1\), \(\beta B<1\) and suppose that G is a weak (A,\(\alpha)\)-expander. Then, given any large \(U\subseteq V\), \(| U| \geq c\cdot | V|\) where \(c=[1-\alpha (A-B)]/(1-\beta B)\), one can find a small \(T\subseteq V\), \(| T| <\alpha | V|\), such that G is a (B,\(\beta)\)-expander from \(V\setminus T\to U\), i.e., expansion in weak (A,\(\alpha)\)-expander graphs is almost uniform. This result is of independent interest.