Deterministic counting Lovász local lemma beyond linear programming

We give a simple combinatorial algorithm to deterministically approximately count the number of satisfying assignments of general constraint satisfaction problems (CSPs). Suppose that the CSP has domain size = (1), each constraint contains at most = (1) variables, shares variables with at most Δ = (1) constraints, and is violated with probability at most by a uniform random assignment.

e algorithm returns in polynomial time in an improved local lemma regime: 2 • • • Δ 5 ≤ 0 for a suitably small absolute constant 0 .

Here the key term Δ 5 improves the previously best known Δ 7 for general CSPs [JPV21b] and Δ 5.714 for the special case of -CNF [JPV21a, HSW21].

Our deterministic counting algorithm is a derandomization of the very recent fast sampling algorithm in [HWY22]. It departs substantially from all previous deterministic counting Lovász local lemma algorithms which relied on linear programming, and gives a deterministic approximate counting algorithm that straightforwardly derandomizes a fast sampling algorithm, hence unifying the fast sampling and deterministic approximate counting in the same algorithmic framework.

To obtain the improved regime, in our analysis we develop a refinement of the 2, 3-trees that were used in the previous analyses of counting/sampling LLL. Similar techniques can be applied to the previous LP-based algorithms to obtain the same improved regime and may be of independent interests.