Sampling constraint satisfaction solutions in the local lemma regime

FENG, KUN HE, AND YITONG YIN A . We give a Markov chain based algorithm for sampling almost uniform solutions of constraint satisfaction problems (CSPs). Assuming a canonical se ing for the Lovász local lemma, where each constraint is violated by a small number of forbidden local configurations, our sampling algorithm is accurate in a local lemma regime, and the running time is a fixed polynomial whose dependency on is close to linear, where is the number of variables. Our main approach is a new technique called state compression, which generalizes the "mark/unmark" paradigm of Moitra [Moi19], and can give fast local-lemma-based sampling algorithms. As concrete applications of our technique, we give the current best almost-uniform samplers for hypergraph colorings and for CNF solutions.