Chicago Journal of Theoretical Computer Science

Volume 2012

Article 2

Published by the Department of Computer Science, The University of Chicago.

Minimum and maximum against k lies

Michael Hoffman
Institute of Theoretical Computer Science
ETH Zürich, Switzerland

Jiří Matoušek
Department of Applied Mathematics
Charles University, Prague, Czech Republic, and
Institute of Theoretical Computer Science
ETH Zürich, Switzerland

Yoshio Okamoto
Department of Communication Engineering and Informatics
University of Electro-Communications, Japan

Philipp Zumstein
University Library
University of Trier, Germany

July 16, 2012


A neat 1972 result of Pohl asserts that ceiling(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. The set is accessed via an oracle for pairwise comparisons. More recently, the problem has been studied in the context of the Rényi--Ulam liar games, where the oracle may give up to k false answers. For large k, an upper bound due to Aigner shows that (k+BigO(sqrt{k}))n comparisons suffice. We improve on this by providing an algorithm with at most (k+1+C)n+BigO(k^3) comparisons for some constant C. A recent result of Pálvölgyi provides a lower bound of the form (k+1+0.5)n-D_k, so our upper bound for the coefficient of n is tight up to the value of C.

Submitted November 26,2010, revised June 20, 2012, 2, published July 1, 2012.

DOI: 10.4086/cjtcs.2012.002

[] Volume 2012, Article 1 [] Volume 2012, Article 3
[back] Volume 2012 [back] Published articles
[CJCTS home]