Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Ihe expected running time of our algorithm is near-linear in n and a fixed polynomial in $\Delta$, where n is the number of variables and $\Delta$ is the max degree …