Towards the sampling Lov\'asz Local Lemma

arXiv2011.12196MaRDI QIDQ6354469FDOQ6354469

Authors: Vishesh Jain, Huy-Tuan Pham, Thuy Duong Vuong 

Publication date: 24 November 2020

Abstract: Let $Phi=(V,mathcalC)$ be a constraint satisfaction problem on variables $v_1,dots,v_n$ such that each constraint depends on at most $k$ variables and such that each variable assumes values in an alphabet of size at most $[q]$. Suppose that each constraint shares variables with at most $Delta$ constraints and that each constraint is violated with probability at most $p$ (under the product measure on its variables). We show that for $k,q=O(1)$, there is a deterministic, polynomial time algorithm to approximately count the number of satisfying assignments and a randomized, polynomial time algorithm to sample from approximately the uniform distribution on satisfying assignments, provided that [Ccdot q^{3}cdot k cdot p cdot Delta^{7} < 1, quad ext{where }C ext{ is an absolute constant.}] Previously, a result of this form was known essentially only in the special case when each constraint is violated by exactly one assignment to its variables. For the special case of $k$-CNF formulas, the term $Delt{a}^7$ improves the previously best known $Delt{a}^{60}$ for deterministic algorithms [Moitra, J.ACM, 2019] and $Delt{a}^{13}$ for randomized algorithms [Feng et al., arXiv, 2020]. For the special case of properly $q$-coloring $k$-uniform hypergraphs, the term $Delt{a}^7$ improves the previously best known $Delt{a}^{14}$ for deterministic algorithms [Guo et al., SICOMP, 2019] and $Delt{a}^9$ for randomized algorithms [Feng et al., arXiv, 2020].

This page was built for publication: Towards the sampling Lov\'asz Local Lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6354469)