BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20260329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20261025T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260614T101034Z
UID:6a06d37191b9c076587052@ist.ac.at
DTSTART:20260618T113000
DTEND:20260618T123000
DESCRIPTION:Speaker: Daniel Rutschmann\nAbstract: 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). Bu
 t 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 prio
 r information as a directed acyclic graph G that contains a vertex for eve
 ry 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 Infor
 mation 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.Suc
 h an algorithm is optimal in a very strong sense: Not only is it optimal f
 or every input size n\, but it is optimal for every graph G\; we call such
  an algorithm universally optimal. There are many fundamental problems tha
 t have textbook algorithms with a running time of (n log n). For these pro
 blems\, we ask: Can we design algorithms that run in o(n log n) time on su
 bsets of inputs characterized by a graph G? Can we achieve universal optim
 ality? 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.
LOCATION:Office Bldg West / Ground floor / Foyer seminar room (I21.EG.128)\
 , ISTA
ORGANIZER:joanders@ist.ac.at
SUMMARY:Daniel Rutschmann: TCS Seminar - From Sorting under Partial Informa
 tion to Universal Optimality
URL:https://talks-calendar.ista.ac.at/events/6509
END:VEVENT
END:VCALENDAR