Sampling Lov'asz Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time

We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Suppose that the CSP has n variables with domain size at most q, each constraint contains at most k variables, shares variables with at most Delta constraints, and is violated with probability at most p by a uniform random assignment. The algorithm returns an almost uniform satisfying assignment in expected poly(q,k,Delta)·tildeO(n) time, as long as a local lemma condition is satisfied: [ k· p· q2· Delta5≤ C0quadfor a suitably small absolute constant C0. ] Previously, under similar local lemma conditions, sampling algorithms with running time polynomial in both n and Delta were only known for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations. The key term Delta5 in our local lemma condition also improves the previously best known Delta7 for general CSPs [JPV21b] and Delta5.714 for atomic CSPs, including the special case of k-CNF [JPV21a, HSW21]. Our sampling approach departs from previous fast algorithms for sampling LLL, which were based on Markov chains. A crucial step of our algorithm is a recursive marginal sampler that is of independent interests. Within a local lemma regime, this marginal sampler can draw a random value for a variable according to its marginal distribution, at a cost independent of the size of the CSP.