After the note on my Bachelor's thesis, I decided to talk about my Master's thesis in computational complexity. The thesis concern is the complexity of solving certain kinds of infinite games on finite graphs, with special emphasis on Parity Games (Archived) and Mean-Payoff Games. For parity games a breakthrough in their solution complexity was obtained some years ago, while mean-payoff games are thought to be much more difficult to solve, and only subexponential algorithms are known.

In the thesis, together with my supervisor Marcello Mamino, we defined a new type of graph game which is of intermediate complexity between parity and mean-payoff games, and we presented algorithms to solve it.

Dopo aver pubblicato qualche tempo fa il materiale della mia tesi triennale, ho deciso di mettere online anche il colloquio del mio quarto anno in Normale (Archived), che tratta della derandomizzazione dei giochi di Arthur-Merlin (Archived).