D. Achlioptas

A sampling Lov\'{a}sz Local Lemma

We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\mathrm e p(\Delta+1)^2\le1$, where $p$ is the largest constraint-violation probability under the uniform product distribution, and $\Delta$ is the maximum degree of the dependency graph. The algorithm...