Towards the sampling Lovasz Local Lemma

Let Phi = (V, C) be a constraint satisfaction problem on variables v(1), ..., v(n) 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. constraints and that each constraint is violated with probability at most Delta (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.q(2).k.p.Delta(7) < 1, 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 Delta(7) improves the previously best known Delta(60) for deterministic algorithms [Moitra, J.ACM, 2019] and Delta(13) for randomized algorithms [Feng, Guo, Yin, and Zhang, STOC 2021]. For the special case of properly q-coloring k-uniform hypergraphs, the term Delta(7) improves the previously best known Delta(14) for deterministic algorithms [Guo, Liao, Lu, and Zhang, SICOMP, 2019] and Delta(9) for randomized algorithms [Feng, Guo, Yin, and Zhang, STOC 2021].

Automated summary

This study introduces a new algorithm for solving constraint satisfaction problems, capable of accurately calculating the number of satisfying assignments and sampling from approximately uniform distributions. The algorithm outperforms previous best known algorithms in several specific cases.