## Oberseminar mathematische Logik

### Organizers

- Dr. Peter Holy
- Prof. Dr. Peter Koepke
- Dr. Philipp Lücke
- Dr. Philipp Schlicht

### 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.

### 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