In the latest months, I've been dealing with interviews from multiple companies. In these, I was frequently asked complex probability brainteasers, which are however quite easy to solve using generating functions, so I thought that I could detail the gist of the method in a post, even though the method is obviously contained inside the standard reference on the matter: generatingfunctionology (Archived).

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

Dopo qualche anno sono incappato nel materiale che avevo prodotto per la mia tesi triennale, e ho deciso di renderlo disponibile online. L'argomento della tesi è l'equazione di Pell (Archived) e i metodi di soluzione basati sulle frazioni continue (Archived), sia nel caso classico sugli interi che nel più recente caso polinomiale.