A Sampling Lovász Local Lemma for Large Domain Sizes

Abstract

We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime: $$p{D}^{2+o_q(1)}\lesssim 1.$$ When the domain size $q$ of each variable becomes sufficiently large, this almost matches the known lower bound $p{D}^2\gtrsim 1$ for approximate counting and sampling solutions to atomic CSPs [Bezáková et al, SICOMP '19; Galanis, Guo, Wang, TOCT '22], thus establishing an almost tight sampling Lovász local lemma for large domain sizes.