Towards the sampling Lovász Local Lemma
Vishesh Jain, Huy Tuan Pham, Thuy Duong Vuong · 2022
Let$\Phi=(V, \mathcal{C})$be a constraint satisfaction problem on variables$v_{1}, \ldots, 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$\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\cdot q^{2}\cdot k\cdot p\cdot\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].