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:

When the domain size of each variable becomes sufficiently large, this almost matches the known lower bound 2 1 for approximate counting and sampling solutions to atomic CSPs [BGG + 19, GGW22], thus establishing an almost tight sampling Lovász local lemma for large domain sizes. Contents 5 1 for counting/sampling LLL [HWY23a].

Remark 1.4 (non-uniform width). Condition 1 does not involve the width , making it applicable to CSP formulas with non-uniform widths. is aspect is particularly desirable from the LLL perspective. Previously, such generality was only a ained in [FHY21] under the local lemma condition 350