Towards the sampling Lovász Local Lemma

Abstract: For a constraint satisfaction problem which satisfies the condition of the Lovász local lemma (LLL), the celebrated algorithm of Moser and Tardos allows one to efficiently find a satisfying assignment. In the past few years, much work has gone into understanding whether one can efficiently sample from (approximately) the uniform distribution on satisfying assignments under LLL-like conditions. I will discuss recent progress on this problem, joint with Huy Tuan Pham (Stanford) and Thuy Duong Vuong (Stanford).

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.