Computer Science/Discrete Mathematics Seminar II

The tasks of finding and randomly sampling solutions of constraint satisfaction problems over discrete variable sets arise naturally in a wide variety of areas, among them artificial intelligence, bioinformatics and combinatorics, and further have deep connections to statistical physics.

In this first talk of the series, I'll cover some recent results regarding algorithms for finding and sampling solutions of constraint satisfaction problems, which are inspired by the Lovasz Local Lemma. The latter is a powerful tool in probabilistic combinatorics, guaranteeing the existence of configurations that avoid a collection of "bad" events that are mostly independent and have low probability.