{"id":"arxiv/2608.08616","url":"https://arxiv.org/abs/2608.08616","tags":["cs.DS","cs.DM","math.PR"],"score":0,"title":"A Counting and Sampling Lovász Local Lemma","domain":"cs.DS","source":"arxiv","authors":["Hongyang Liu","Chunyang Wang","Yitong Yin","Yiyao Zhang","Can Zhou"],"reviews":0,"subject":"cs.DS","summary":"We establish counting and sampling analogues of the Lovász Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime $$4 \\mathrm{e} p (D+1)^2\\leq 1, $$ where $p$ is the maximum constraint violation probability and $D$ is the maximum dependency degree. This condition is tight up to constant factors under $\\mathbf{NP}\\neq\\mathbf{RP}$, matching known hardness bounds for counting and sampling in natural subclasses of CSPs. Our key ingredient is a novel $2$-tree…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-09","reactions":{}}