The entropy compression method for random algorithms

The Lovász Local Lemma (LLL) is one of the most important tools of the celebrated Probabilistic Method in combinatorics. The idea behind it is that, in order to prove the existence of a combinatorial object with some nice properties, one can select such an object at random and provethat it satisfies said properties with non zero probability.

This lemma,since it appeared in 1975, has been used many times in very different settings, including theoretical computer science. An important drawback was for a long time the absence of an efficient algorithm to find the object which existence is guaranteed by the LLL. In a major breakthrough, Moser and Tardos were able in 2010 to design an algorithm which covers most of the application of the LLL.

Perhaps even more importantly, they introduced in this paper a new method called "entropy compression", which has since then been used in several different contexts to prove that some random algorithm terminates.The goal of this lecture will be to present this method.

We will first give an overview of Moser and Tardos's algorithm before presenting different examples of situations where this technique can be applied.

Trial lecture from 11:15-12.

Technical session from 12:30-14:30.

https://uib.zoom.us/j/61193541130?pwd=UWpBN0Fsa3Z4cXNqSExTd2tuZkdVUT09