Understanding the quasipolynomial time algorithms for parity games: upper and lower bounds

11^th December 2018, 14:00 H223
Nathanaël Fijalkow
CNRS, LaBRI, Bordeaux and The Alan Turing Institute of data science and artificial intelligence, London

Abstract

In this talk I will show a unifying approach for the three recent quasipolynomial time algorithms for parity games. The first outcome is to give simple presentations and proofs of the algorithms. The second and main outcome is to prove lower bounds in this framework.

This talk is based on joint works with Wojciech Czerwiński, Laure Daviaud, Marcin Jurdziński, Ranko Lazić, and Paweł Parys to be presented at SODA'2019, as well as more recent work with Thomas Colcombet.