Sampling and Approximately Counting CNF Formula Solutions in the Local Lemma Regime

In this talk, I will describe recent progress on sampling and approximately counting CNF formula solutions. Given a CNF formula in which each clause has k variables and each variable belongs to at most d clauses, if a local lemma-type condition k = Ω(log d) is satisfied, we can provide efficient algorithms for generating almost uniform random solutions and for approximately counting the number of solutions. Our sampling algorithm uses the MCMC method on a projected space. The randomized approximate counting algorithm can be derived from the standard reduction. Additionally, we introduce a new technique that derandomizes certain MCMC algorithms and obtains deterministic approximate counting algorithms.