Sampling Lovász Local Lemma for General Constraint Satisfaction Solutions in Near-Linear Time

Abstract

We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. The expected running time of our algorithm is near-linear in $n$ and a fixed polynomial in $\Delta$, where $n$ is the number of variables and $\Delta$ is the max degree of constraints. Previously, up to similar conditions, sampling algorithms with running time polynomial in both $n$ and $\Delta$, only existed for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations. Our sampling approach departs from all 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 local cost independent of the size of the CSP.

Chunyang Wang

Ph.D Student

I am currently a fifth-year Ph.D student in the Theory Group in the Department of Computer Science and Technology at Nanjing University. My research interest lies in a broad aspect of computer science. Currently, I am focusing on algorithms for counting and sampling.

Yitong Yin

Professor

I am a professor in the Theory Group in the Department of Computer Science and Technology at Nanjing University. I am interested in Theoretical Computer Science.