Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Sven Schewe

LFCS Seminar: Sven Schewe

— filed under:

Beautiful games you cannot stop playing

  • LFCS Seminar
When Apr 03, 2012
from 04:00 PM to 05:00 PM
Where IF 4.31-4.33
Add event to calendar vCal

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.
But be careful: don't get hooked!
Document Actions