On the sampling Lov\'asz Local Lemma for atomic constraint satisfaction problems

Understand

We study the problem of sampling an approximately uniformly random satisfying assignment for atomic constraint satisfaction problems i.e.

• where each constraint is violated by only one assignment to its variables.
• Let $p$ denote the maximum probability of violation of any constraint and let $\Delta$ denote the maximum degree of the line graph of the constraints.
• Our main result is a nearly-linear (in the number of variables) time algorithm for this problem, which is valid in a Lov\'asz local lemma type regime that is considerably less restrictive compared to previous works.