Sven Schewe

Date: 17:00, Thursday, October 29, 2015
Speaker: Sven Schewe
Venue: IST Austria

Parity games are simple two player games played on a finite arena that have all that it takes to attract the attention of researchers: it is a simple problem which is hard to analyse – a pocket version of P vs. NP. Parity games are known to be in UP, CoUP, PPAD, PLS, and some more classes besides, but whether or not they are tractable has proven to be a rather elusive question. What is more, when you study them, you will have the constant feeling that there is a polynomial time solution just around the corner, although it dissolves into nothingness when you look more closely. This talk is about the beauty of these games, the relevant algorithmic approaches and their complexity and development over time. But be careful: they are addictive, don’t get hooked!

Posted in RiSE Seminar