Abstract
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: $$q^2\cdot k\cdot p\cdot\Delta^5\le C_0\quad\text{for a suitably small absolute constant }C_0.$$ Here the key term $\Delta^5$ improves the previously best known $\Delta^7$ for general CSPs [JPV21b] and $\Delta^{5.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á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.
Kun He
Associate Professor
I am an Associate Professor in the School of Information at Renmin University of China. My research focuses on algorithms and probability, particularly probabilistic methods, sampling, quantum computing, and theoretical machine learning.
Chunyang Wang
Postdoc
I am Chunyang Wang (王淳扬), currently a project researcher (postdoc) at the National Institute of Informatics (NII), hosted by Prof. Yuichi Yoshida. My research interests broadly lie in theoretical computer science, especially algorithms for counting and sampling and algorithmic stability.
Yitong Yin
Professor
I am a professor in the Theory Group at the School of Computer Science, Nanjing University. My research interests include randomized algorithms and computational sampling and counting, data structures and lower bounds, and parallel and distributed computing.