Joint ICE-TCS@Reykjavik University/GSSI virtual seminar: Karoliina Lehtinen

Parity Games -- the quasi-polynomial era

  • 25.5.2020, 13:30 - 14:10

Karoliina Lehtinen (University of Liverpool, UK) will deliver a joint ICE-TCS@Reykjavik University/GSSI virtual seminar on Monday, 25 May, at 13:30 GMT/15:30 Italian time.

The title and abstract of the talk, which will survey recent developments on quasi-polynomial algorithms for solving parity games, are below. The link for the talk is


Title: Parity Games -- the quasi-polynomial era

Speaker: Karoliina Lehtinen (University of Liverpool, UK)


Parity games are central to the verification and synthesis of reactive systems: various model-checking 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 survey these many developments and present one particularly straight-forward quasi-polynomial algorithm in more detail.

Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á eða með því að senda tölvupóst á netfangið:
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our or send an e-mail: