arXiv preprint ·
A general counting and sampling Lovász local lemma
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 constraints are satisfied, and an approximate sampler, running in polynomial expected time, for the product distribution conditioned on this event. The degree of the polynomial in the running time is independent of the domain sizes, constraint sizes, or degree of the dependency graph. Up to the choice of the constant $c$, our condition on $p_a$ matches known hardness results. Our work builds on the method of Liu, Wang, Yin, Zhang, and Zhou, who obtained an FPRAS for the probability of satisfaction in the setting of the symmetric Lovász Local Lemma. Our sampling result is new even in this special case.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Vector Balancing in Polynomial Time
Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
Dual-GNN Multilevel Coarsening for Maximum Independent Set
Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
PermuFormer: Multi-Task Pretraining for Permutation Representation in Algebraic Combinatorics
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.