Deterministic counting Lov'asz 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 q=O(1), each constraint contains at most k=O(1) variables, shares variables with at most Delta=O(1) constraints, and is violated with probability at most p by a uniform random assignment. The algorithm returns in polynomial time in an improved local lemma regime: [ q2· k· p·Delta5≤ C0quadfor a suitably small absolute constant C0. ] Here the key term Delta5 improves the previously best known Delta7 for general CSPs [JPV21b] and Delta5.714 for the special case of k-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'asz 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.