LFCS Seminar: Sven Schewe
Beautiful games you cannot stop playing
What 


When 
Apr 03, 2012 from 04:00 PM to 05:00 PM 
Where  IF 4.314.33 
Add event to calendar 
vCal iCal 
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, and some weirder classes besides, but whether or not they are in P has proven to be a rather elusive question. What is more, when you work with them, you will have the constant feeling that there is a polynomial 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. I'll focus on three results:
 parity games can be solved in n^{p/3} and exp(sqrt(n log n)),
 parity games with bounded tree width are in NC^2, and
 a strategy improvement algorithm that finds and evaluates the optimal greedy update step in quasi linear time.