BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:6932@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20191024T110000
DTEND;TZID=Europe/Paris:20191024T123000
DTSTAMP:20241120T202629Z
URL:https://www.i2m.univ-amu.fr/evenements/karoliina-lehtinen-quasi-polyno
 mial-techniques-for-parity-games-and-and-other-problems/
SUMMARY:Karoliina Lehtinen (University of Liverpool): Quasi-polynomial tech
 niques for parity games and and other problems
DESCRIPTION:Karoliina Lehtinen: Séminaire commun avec les équipes MoVe et
  Lirica du LIS\nParity 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 problem
 s 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.\n\nIn 2017 a ma
 jor breakthrough occurred: parity games are solvable in quasi-polynomial t
 ime. Since then\, several seemingly very distinct quasi-polynomial algorit
 hms have been published\, and some of these ideas have been used to solve 
 other automata-theoretic problems.\n\nIn this talk\, I will give an overvi
 ew of these developments and the state-of-the art\, with a slight automata
 -theoretic bias.\n\nBibliography: Roughly\, this talk is based on developm
 ents presented in the following papers\, by myself and others:\n\n* Univer
 sal trees grow inside separating automata: Quasi-polynomial lower bounds f
 or parity games. W. Czerwiński\, L. Daviaud\, N. Fijalkow\, M. Jurdzińsk
 i\, R. Lazić\, P. Parys. SODA 2019\n* Improving the complexity of Parys
 ’ recursive algorithm. K. Lehtinen\, S. Schewe and D. Wojtczak. Unpublis
 hed.\n* Parity Games: Zielonka's Algorithm in Quasi-polynomial Time. P. Pa
 rys. MFCS 2019.\n* Alternating weak automata from universal trees. L. Davi
 aud\, M. Jurdziński and K. Lehtinen CONCUR 2019\n* On the way to alternat
 ing weak automata. U. Boker and K. Lehtinen. FSTTCS 2018.\n* A modal μ pe
 rspective on solving parity games in quasi-polynomial time. K. Lehtinen. L
 ICS 2018\n* Succinct progress measures for solving parity games. M. Jurdzi
 ński and R. Lazić. LICS 2017.\n* Deciding Parity Games in Quasipolynomia
 l Time. C. Calude\, S. Jain\, B. Khoussainov\, W. Li and F. Stephan. STOC 
 2017.\n\n&nbsp\;
ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2
 020/01/Karoliina_Lehtinen.jpg
CATEGORIES:Séminaire,Logique et Interactions
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20190331T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR