Towards the sampling Lov'asz Local Lemma

Let Phi = (V, C) be a constraint satisfaction problem on variables v1,dots, vn such that each constraint depends on at most k variables and such that each variable assumes values in an alphabet of size at most [q]. Suppose that each constraint shares variables with at most Delta constraints and that each constraint is violated with probability at most p (under the product measure on its variables). We show that for k, q = O(1), there is a deterministic, polynomial time algorithm to approximately count the number of satisfying assignments and a randomized, polynomial time algorithm to sample from approximately the uniform distribution on satisfying assignments, provided that [C· q3· k · p · Delta7 < 1, quad where C is an absolute constant.] Previously, a result of this form was known essentially only in the special case when each constraint is violated by exactly one assignment to its variables. For the special case of k-CNF formulas, the term Delta7 improves the previously best known Delta60 for deterministic algorithms [Moitra, J.ACM, 2019] and Delta13 for randomized algorithms [Feng et al., arXiv, 2020]. For the special case of properly q-coloring k-uniform hypergraphs, the term Delta7 improves the previously best known Delta14 for deterministic algorithms [Guo et al., SICOMP, 2019] and Delta9 for randomized algorithms [Feng et al., arXiv, 2020].