A general counting and sampling Lov\'asz local lemma
En palabras de los autores
Consider a constraint satisfaction problem on finitely many independent random variables with dependency graph . Let be the violation probability of a constraint and the set of constraints at distance one or two from in . Suppose that, there exists such that, for a sufficiently small universal constant , and for all , \[ 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\'asz 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 , our condition on 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\'asz Local Lemma. Our sampling result is new even in this special case.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.