BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quasi-polynomial solutions for parity games and other problems - K
 aroliina Lehtinen\, Christian-Albrechts University of Kiel
DTSTART:20180914T130000Z
DTEND:20180914T140000Z
UID:TALK108619@talks.cam.ac.uk
CONTACT:Victor Gomes
DESCRIPTION:Parity games are infinite two-player games\, which are used in
  verification\, automata theory\, and reactive synthesis.\nSolving parity 
 games -- that is\, deciding which player has a winning strategy -- is one 
 of the few problems known to be in\nboth UP and co-UP yet not known to be 
 in P. So far\, the quest for a polynomial algorithm has lasted over 25 yea
 rs.\n Last year\, a major breakthrough occurred: parity games are solvable
  in quasi-polynomial time.\n\nFrom an automata-perspective\, solving parit
 y games can be done by transforming alternating parity word automata into 
 alternating weak automata. \nFrom a logician's perspective\, solving parit
 y games can be done by finding a mu-calculus formula that recognises the w
 inning region of a player in the parity game. \nThen\, the size blow-up of
  the automaton in the first case\, and the complexity of the formula in th
 e second case\, determine the complexity of the consequent algorithm for s
 olving parity games.\n\nIn this talk\, I present a quasi-polynomial soluti
 on for all three problems\, based on playing parameterised games on parity
 -game arenas.\n\n\nThis talk is based on "A modal mu perspective on solvin
 g parity games in quasi-polynomial time"\, presented at LICS'18 and subseq
 uent work with Udi Boker on weak automata.
LOCATION:FW26
END:VEVENT
END:VCALENDAR