Many computational problems of interest are difficult, in the sense that no efficient (polynomial time) algorithm solving them is known. This is for instance the case for the traveling salesman problem, who has to find a shortest circuit visiting a given set of cities: No fast algorithm has been found for this apparently simple problem when the number of cities is large. This is also the case for the boolean satisfiability problem, that of testing whether a formula in boolean logic can be satisfied. For a large family of such problems, most researchers suspect that there is simply no efficient algorithm. This is the famous "P?=?NP question, carrying a $1,000,000 prize from the Clay Mathematics Institute for the first correct solution.

Some of these problems become easier when we have extra information on the input. For instance, if each variable of our boolean formula does not appear "too often" then we can simply choose at random the values of the variables and the formula will be satisfied with non zero probability. This is a consequence of the Lovasz Local Lemma, a powerful tool in Combinatorics. However, this does not help us finding a good assignment for the variables.

Recently, a breakthrough was achieved by two researchers, Robin Moser et Gabor Tardos: They obtained a fully constructive proof the Lovasz Local Lemma, resulting in efficient algorithms for finding the solutions whose existence are guaranteed by the lemma. To do so, they developed a brand new technique, the "entropy compression" method.

It quickly appeared that this technique was not limited to the Local Lemma but could more generally be applied to obtain new combinatorial results. This opens up a new and exciting venue for research in Combinatorics. By exploring the power and limits of compression arguments, the goal is to obtain general purpose tools that can be used to solve a large variety of combinatorial problems.

Spokesperson

JORET Gwenaël
Informatics Department
Faculty of Sciences

Dates
Created on August 31, 2018