Sampling Constraint Satisfaction Solutions in the Local Lemma Regime

Understand

We give a Markov chain based algorithm for sampling almost uniform solutions of constraint satisfaction problems (CSPs).

• Assuming a canonical setting for the Lov\'asz 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 $n$ is close to linear, where $n$ is the number of variables.
• Our main approach is a new technique called state compression, which generalizes the "mark/unmark" paradigm of Moitra (Moitra, JACM, 2019), 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.