Fast Order Statistics with Group Inequality Testing

Suppose that a group test operation is available for checking order relations in a set, can this speed up problems like finding the minimum/maximum element, determining the rank of element, and computing order statistics? We consider a one-sided group inequality test to be available, where queries are of the form $u \le_Q V$ or $V \le_Q u$, and the answer is `yes' if and only if there is some $v \in V$ such that $u \le v$ or $v \le u$, respectively. We restrict attention to total orders and focus on query-complexity; for min or max finding, we give a Las Vegas algorithm that makes $\mathcal{O}(\log^2 n)$ expected queries. We observe that rank determination can be solved with existing ``defect-counting'' algorithms, but also give a simple Monte Carlo approximation algorithm with expected query complexity $\tilde{\mathcal{O}}(\frac{1}{δ^2} \log \frac{1}ε)$, where $1-ε$ is the probability that the algorithm succeeds and we allow a relative error of $1 \pm δ$ for $δ> 0$ in the estimated rank. We then give a Monte Carlo algorithm for approximate selection that has expected query complexity $\tilde{\mathcal{O}}(\frac{1}{δ^4}\log \frac{1}{εδ^2} )$; it has probability at least $\frac{1}{2}$ to output an element $x$, and if so, $x$ has the desired approximate rank with probability $1-ε$. Keywords: Order statistics, Group inequality testing, Randomized algorithms