BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20200329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20191027T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260406T042344Z
UID:5df8e51f2d6bb287689470@ist.ac.at
DTSTART:20200121T090000
DTEND:20200121T100000
DESCRIPTION:Speaker: Karoliina Lehtinen\nhosted by Krish Chatterjee\nAbstra
 ct: Parity games are central to the verification and synthesis of reactive
  systems: various model-checking\, realisability and synthesis problems re
 duce to solving these games. Solving parity games -- that is\, deciding wh
 ich player has a winning strategy -- is one of the few problems known to b
 e in both UP and co-UP yet not known to be in P. So far\, the quest for a 
 polynomial algorithm has lasted over 25 years.In 2017 a major breakthrough
  occurred: parity games are solvable in quasi-polynomial time. Since then\
 , several seemingly very distinct quasi-polynomial algorithms have been pu
 blished\, both by myself and others\, and some of the novel ideas behind t
 hem have been applied to address other problems in automata theory.In this
  talk\, I will give an overview of these developments\, including my own c
 ontribution to them\, and the state-of-the art\, with a slight automata-th
 eoretic bias.
LOCATION:Mondi Seminar Room 2\, Central Building\, ISTA
ORGANIZER:tguggenb@ist.ac.at
SUMMARY:Karoliina Lehtinen: Parity Games -- the quasi-polynomial era
URL:https://talks-calendar.ista.ac.at/events/2465
END:VEVENT
END:VCALENDAR