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. Suppose that the CSP has $n$ variables with domain size at most $q$, each constraint contains at most $k$ variables, shares variables with at most $\Delta$ constraints, and is violated with probability at most $p$ by a uniform random assignment. The algorithm returns an almost uniform satisfying assignment in expected $\mathrm{poly}(q,k,\Delta)\cdot\tilde{O}(n)$ time, as long as a local lemma condition is satisfied: $$k\cdot p\cdot q^2\cdot \Delta^5\le C_0\quad\text{for a suitably small absolute constant }C_0.$$ Previously, under similar local lemma conditions, sampling algorithms with running time polynomial in both $n$ and $\Delta$ were only known for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations. The key term $\Delta^5$ in our local lemma condition also improves the previously best known $\Delta^7$ for general CSPs [JPV21b] and $\Delta^{5.714}$ for atomic CSPs, including the special case of $k$-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.

Kun He

Associate Professor

I am an Associate Professor in the School of Information at Renmin University of China. My research focuses on algorithms and probability, particularly probabilistic methods, sampling, quantum computing, and theoretical machine learning.

Chunyang Wang

Postdoc

I am Chunyang Wang (王淳扬), currently a project researcher (postdoc) at the National Institute of Informatics (NII), hosted by Prof. Yuichi Yoshida. My research interests broadly lie in theoretical computer science, especially algorithms for counting and sampling and algorithmic stability.

Yitong Yin

Professor

I am a professor in the Theory Group at the School of Computer Science, Nanjing University. My research interests include randomized algorithms and computational sampling and counting, data structures and lower bounds, and parallel and distributed computing.