Alon Orlitsky
Two to Tons: Optimal Maxing, Ranking, and Preference Learning

Maximum selection (maxing) of n objects using n-1 pairwise
comparisons, and sorting (ranking) using O(n log n) pairwise
comparisons are algorithmic staples taught in most introductory
classes and used in a myriad of applications. Recent
preference-learning research has raised renewed interest in these
problems, where the pairwise comparisons are noisy. Yet even for the
simplest comparison models, such as Plackett-Luce, the complexity of
maxing and ranking was known only to a log n factor. We describe a
simple comparison hierarchy that determines the complexity of the two
problems to a constant factor in nearly all cases. We conclude with a
helpful 1-d jigsaw puzzle.  Joint work with Moein Falahatgar, Yi Hao,
Ayush Jain, Venkatadheeraj Pichapati, Vaishakh Ravindrakumar, and
Ananda Theertha Suresh.