# Deterministic counting Lov'asz local lemma beyond linear programming

arXiv: https://arxiv.org/abs/2212.14847 · HTML: https://mlsanity.com/paper/2212.14847/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2022.

## Built on by (most cited first, 4 of 4)

- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [One-Shot Learning for k-SAT](https://mlsanity.com/paper/2502.07135/) (2025)
- [Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm](https://mlsanity.com/paper/2609.15268/) (2026)

## Abstract (arXiv)

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.