A large body of work studies the complexity of selecting the
j-th largest element in an arbitrary set of n elements (a.k.a.
the select(j) operation). In this work, we study the
complexity of select in data that is partially structured by
an initial preprocessing stage and in a data structure ... more >>>