Computer Science/Discrete Mathematics Seminar II

Topic: Constraint Satisfaction Problems and Probabilistic Combinatorics I

Speaker: Fotios Illiopoulos

Affiliation: Member, School of Mathematics

Date & Time: Tuesday November 19th, 2019, 10:30am - 12:30pm

Location: Simonyi Hall 101


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.