Oberseminar mathematische Logik
Time and location
Mondays 16.30-18.00 in room 0.008, Endenicher Allee 60.
The participants of the seminar are welcome for coffee and tea in the Plückerraum 1.012 at 16.00 before the talks.
- 24 April: Frank Stephan (Singapore) - Deciding parity games in quasipolynomial time
Parity games are games on finite graphs where each node has a value. Two players, Anke and Boris, move alternately a marker through the graph and plays between the two players have infinite duration. One determines the winner of such an infinite play by taking the largest value of a node which is visited infinite often; if this value is even then the first player Anke wins else the second player Boris wins. An important question is to determine the player who has a winning strategy in such games. One evaluates such algorithms in terms of the number n of nodes and number m of colours and other possible parameters. Prior work has given algorithms with runtime O(nm/3) and nO(Sqrt(n)). The talk will present an improved quasipolynomial algorithm with runtime O(nlog(m)+8)which determines the winner and the winning strategy. Furthermore, if m < log(n), one can determine the winner in time O(n5); thus the problem is fixed-parameter tractable and the algorithm brings it from the prior known complexity class XP into FPT. This is joint work with Cristian Calude, Bakhadyr Khoussainov, Li Wei and Frank Stephan.
- 01 May: no seminar
- 08 May: Chris Lambie-Hanson (Bar-Ilan) - tba
- 15 May: tba
- 22 May: tba
- 05 June: no seminar
- 12 June: Stefan Hoffelner (Vienna) - tba
- 19 June: tba
- 26 June: tba
- 03 July: no seminar
- 10 July: tba
- 17 July: tba
- 24 July: tba