Minimum and Maximum against k Lies

We consider an n-element set X with an unknown total ordering. The ordering can be accessed via an oracle that, given two elements x,y in X, tells us whether x < y or x > y. It is easy to see that the minimum element of X can be found using(n-1) comparisons. One of the nice little surprises in computer science is that if we want to find both the minimum and the maximum, we can do significantly better than finding the minimum and the maximum separately. A neat 1972 result of Pohl asserts that (ceil(3n/2)-2) comparisons are sufficient, and also necessary in the worst case, for finding both the minimum and the maximum of an n-element totally ordered set. Here we consider the problem of determining both the minimum and the maximum in the case where the oracle is not completely reliable. It may sometimes give a false answer, but only at most k times during the whole computation, where k is a given parameter. We refer to this model as computation against k lies. Let us stress that we admit repeating the same query to the oracle several times, and each false answer counts as a lie. If repeated queries were not allowed, or if the oracle could always give the wrong answer to a particular query, then the minimum can never be determined accurately. So, for example, if we repeat a given query (2k + 1) times, we always get the correct answer by majority vote. The problem of finding both the minimum and the maximum against k lies was investigated by Aigner, who proved in 1997 that (k + O(k0.5))n comparisons always suffice. In this talk, we will show an improvement on this by providing an algorithm that requires at most (k+1+C)n+O(k3) comparisons for some constant C. The best known lower bounds for the number of comparisons necessary to determine both the minimum and the maximum against k lies have the form (k+1+c_{k})n-D, where D is a small constant and the c_{k} are as follows : c_{0} = 1/2 [Pohl], c_{1} = 23/32, and c_{k} = Omega(2^{-5k/4}) as k goes to infinity.