Jun 18, 2026
TCS Seminar – From Sorting under Partial Information to Universal Optimality
Date: June 18, 2026 |
11:30 am –
12:30 pm
Speaker:
Daniel Rutschmann, ISTA
Location: Office Bldg West / Ground floor / Foyer seminar room (I21.EG.128)
Language:
English
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
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.
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
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.
