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.
Kun He
Researcher
I am a researcher in algorithms and complexity in the School of informatics, Renmin University of China. My research focuses on algorithms and probability. Specifically, my main areas of focus lie in the intriguing realms of probabilistic methods and sampling techniques. Furthermore, I enthusiastically explore the captivating fields of quantum computing and theoretical machine learning. In fact, I possess a broad fascination for theoretical problems within scientific research as a whole.
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.