Sampling Lovász 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 variables with domain size at most , each constraint contains at most variables, shares variables with at most Δ constraints, and is violated with probability at most by a uniform random assignment. e algorithm returns an almost uniform satisfying assignment in expected poly( , , Δ) • ˜ ( ) time, as long as a local lemma condition is satisfied:

Previously, under similar local lemma conditions, sampling algorithms with running time polynomial in both and Δ were only known for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations. e key term Δ 5 in our local lemma condition also improves the previously best known Δ 7 for general CSPs [JPV21b] and Δ 5.714 for atomic CSPs, including the special case of -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. Contents 1. Introduction 1 2. Notations for CSP 5 3. e Sampling Algorithm 6 4. Preliminary on Lovász Local Lemma 10 5. Correctness of Sampling 11 6. Efficiency of Sampling 15 7. e Generalized 2, 3-Tree 29 8. Conclusion and Open Problems 45 Acknowledgement 45 References 46 Appendix A. A Bernoulli Factory for Margin Overflow 48 Appendix B. Basic Properties of Variable/Constraint A ributes along Path 50