Tight Bounds for Sorting Under Partial Information.

Sorting is one of the fundamental algorithmic problems in theoretical computer science. It has a natural generalization, introduced by Fredman in 1976, called sorting under partial information. The input consists of: –a ground set X of size n, –a partial oracle OF (where partial oracle queries for any (xi,xj) output whether xi≺Pxj, for some partial order P), –a linear oracle OL (where linear oracle queries for any (xi,xj) output whether xi<Lxj and the order L extends P) The goal is to recover the linear order L on X using the fewest number of linear oracle queries. In this problem, we measure algorithmic complexity through three metrics: the number of linear oracle queries to OL, the number of partial oracle queries to OP, and the time spent (the number of algorithmic instructions required to identify for which pairs (xi,xj) a partial or linear oracle query is performed). Let e(P) denote the number of linear extensions of P. Any algorithm requires worst-case log2e(P) linear oracle queries to recover the linear order on X. In 1984, Kahn and Saks presented the first algorithm that uses Θ(loge(P)) linear oracle queries (using O(n2) partial oracle queries and exponential time). Since then, both the general problem and restricted variants have been consistently studied. The state-of-the-art for the general problem is by Cardinal, Fiorini, Joret, Jungers and Munro who at STOC'10 manage to separate the linear and partial oracle queries into a preprocessing and query phase. They can preprocess P using O(n2) partial oracle queries and O(n2.5) time. Then, given OL, they uncover the linear order on X in Θ(loge(P) linear oracle queries and O(n+loge(P)) time - which is worst-case optimal in the number of linear oracle queries but not in the time spent. We present the first algorithm that uses a subquadratic number of partial oracle quer