On 25 April at 14:00, Turing Award Laureate Robert Tarjan will give a public lecture titled “Fast and Simple Sorting Using Partial Information”. The lecture will take place at the Delta Study Building, room 1037, and everyone is welcome to attend.
The presentation is part of the Estonian–Latvian Computer Science Theory Days 2026.
Abstract
We consider the problem of sorting a set of items having an unknown total order by doing binary comparisons of the items, given the outcomes of some pre-existing comparisons. We present a simple algorithm with a running time of O(m + n + log T), where n, m, and T are the number of items, the number of pre-existing comparisons, and the number of total orders consistent with the outcomes of the pre-existing comparisons, respectively. The algorithm does O(log T) comparisons.
Both our time and comparison bounds are best possible up to constant factors, thus resolving a problem which has been open since 1978 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of O(log T) on the number of comparisons has a non-linear time bound and is much more complicated. Our algorithm combines two classic algorithms: topological sort and heapsort, with the right kind of heap. This is joint work with Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, and Jakub Tětek.
Biography
Robert Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He has held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, HP, Microsoft, and Intertrust Technologies. He has invented or co-invented many of the most efficient known data structures and graph algorithms. He was awarded the first Nevanlinna Prize from the International Mathematical Union in 1982 for “for outstanding contributions to mathematical aspects of information science,” the Turing Award in 1986 with John Hopcroft for “fundamental achievements in the design and analysis of algorithms and data structures,” the Paris Kanellakis Award in Theory and Practice in 1999 with Daniel Sleator for the invention of splay trees, the 2025 Basic Since Lifetime Award in Information Sciece and Engineering, and many other awards. He is a member of the U.S. National Academy of Sciences, the U. S. National Academy of Engineering, the American Academy of Arts and Sciences, and the American Philosophical Society.
