Upcoming Talks

Ist logo

Parity Games -- the quasi-polynomial era

Date: Tuesday, January 21, 2020 09:00 - 10:00
Speaker: Karoliina Lehtinen (University of Liverpool)
Location: Mondi Seminar Room 2, Central Building
Series: Mathematics and CS Seminar
Host: Krish Chatterjee

Parity games are central to the verification and synthesis of reactive systems: various model-checking, realisability and synthesis problems reduce to solving these games. Solving parity games -- that is, deciding which player has a winning strategy -- is one of the few problems known to be 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 published, both by myself and others, and some of the novel ideas behind them have been applied to address other problems in automata theory.

In this talk, I will give an overview of these developments, including my own contribution to them, and the state-of-the art, with a slight automata-theoretic bias.
Qr image
Download ICS Download invitation
Back to eventlist