TCS Seminar - From Sorting under Partial Information to Universal Optimality
Date
Thursday, June 18, 2026 11:30 - 12:30
Speaker
Daniel Rutschmann (ISTA)
Location
Office Bldg West / Ground floor / Foyer seminar room (I21.EG.128)
Series
Seminar/Talk
Contact
Comparison based sorting is a well understood problem. There are many algorithms that sort n items in O(n log n) comparisons, and this is tight since log(n!) (n log n). But what if you already know that some elements are smaller than others? Can you then sort in fewer than (n log n) comparisons?
We can encode this prior information as a directed acyclic graph G that contains a vertex for every item, and an edge x y if we already know that x < y. If there are e(G) sorted orders (permutations) compatible with G, then any algorithm must perform (log e(G)) comparisons. The problem of Sorting from Partial Information is to match this bound, that is, to design an efficient algorithm that, given the graph G, sorts the items in O(log e(G)) comparisons.
Such an algorithm is optimal in a very strong sense: Not only is it optimal for every input size n, but it is optimal for every graph G; we call such an algorithm universally optimal. There are many fundamental problems that have textbook algorithms with a running time of (n log n). For these problems, we ask: Can we design algorithms that run in o(n log n) time on subsets of inputs characterized by a graph G? Can we achieve universal optimality? This concept applies not only to graph algorithms such as Dijkstra's or Prim's, but also to a wide range of fundamental problems, including set intersection and convex hulls.