A Sampling Lovász Local Lemma for Large Domain Sizes

We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime: \begin{equation*} pD^{2+o_{q}(1)}\lesssim 1.\end{equation*} When the domain size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex> of each variable becomes sufficiently large, this almost matches the known lower bound <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$pD^{2}\lesssim 1$</tex> for approximate counting and sampling solutions to atomic CSPs [1], [2], thus establishing an almost tight sampling Lovasz local lemma for large domain sizes.