Selecting the k largest elements with parity tests ?
In this paper we study the problem of finding the k largest elements of n distinct real numbers. We give a pure combinatorial argument to prove that queries are necessary for any deterministic algorithm using parity tests only. We also present a randomized algorithm with error probability O(1/nc) using only parity tests, where c>1 is any fixed constant.
selection parity tests randomized algorithm lower bound