{"id":"arxiv/2609.23671","url":"https://arxiv.org/abs/2609.23671","tags":["cs.DS","math.CO"],"score":0,"title":"A general counting and sampling Lovász local lemma","domain":"cs.DS","source":"arxiv","authors":["Vishesh Jain","Clayton Mizgerd","Huy Tuan Pham"],"reviews":0,"subject":"cs.DS","summary":"Consider a constraint satisfaction problem $\\mathbf{C}$ on finitely many independent random variables with dependency graph $G$. Let $p_a$ be the violation probability of a constraint $a\\in \\mathbf{C}$ and $N_G^2 (a)$ the set of constraints at distance one or two from $a$ in $G$. Suppose that, there exists $x\\in (0,1)^{\\mathbf{C}}$ such that, for a sufficiently small universal constant $c > 0$, and for all $a \\in \\mathbf{C}$, \\[ p_a \\leq c \\cdot x_a \\prod_{b\\in N_G^2(a)}(1-x_b). \\] Under the above analog of the asymmetric Lovász Local Lemma, we give an FPRAS for the probability that all…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}