A Sampling Lovász Local Lemma for Large Domain Sizes

Chunyang Wang, Yitong Yin

We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regi…