{"ID":22952675,"CreatedAt":"2026-09-17T02:12:05.498442134Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.18712","arxiv_id":"2609.18712","title":"A sampling Lovász Local Lemma","abstract":"We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\\mathrm e p(Δ+1)^2\\le1$, where $p$ is the largest constraint-violation probability under the uniform product distribution, and $Δ$ is the maximum degree of the dependency graph. The algorithm invokes the recent efficient approximate counting algorithm of Liu, Wang, Yin, Zhang, and Zhou as a subroutine and returns a satisfying assignment sampled within total-variation distance $\\varepsilon$ of the uniform distribution in $(n+m/\\varepsilon)^{O(kΔ\\log D)}$ time, where $n$ and $m$ are the numbers of variables and constraints, $D$ is the common domain size, and $k$ bounds the constraint arity.","short_abstract":"We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\\mathrm e p(Δ+1)^2\\le1$, where $p$ is the largest constraint-violation probability under the uniform product distribution, and $Δ$ is the maximum degree of the dependency graph. The algorithm invokes t...","url_abs":"https://arxiv.org/abs/2609.18712","url_pdf":"https://arxiv.org/pdf/2609.18712v1","authors":"[\"Dimitris Achlioptas\"]","published":"2026-09-16T14:19:01Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.PR\"]","methods":"[]","has_code":false}