Constraint Satisfaction Problems and Probabilistic Combinatorics I

Computer Science/Discrete Mathematics Seminar II
Topic:Constraint Satisfaction Problems and Probabilistic Combinatorics I
Speaker:Fotios Illiopoulos
Affiliation:Member, School of Mathematics
Date:Tuesday, November 19
Time/Room:10:30am - 12:30pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2019/1119-FotiosIlliopoulos

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.