The Lovász Local Lemma as Approximate Dynamic Programming

If we assign random values to the variables of a Constraint Satisfaction Problem, the probability we will get a solution is positive, if and only if the instance is satisfiable. Crucially, to establish that the instance is satisfiable any multiplicative underestimation of this probability, no matter how poor, suffices. The Lovász Local Lemma (LLL), a cornerstone of the Probabilistic Method, is a tool for establishing such positive probability lower bounds. In this talk, we will present a new, computational view of the LLL which leads to significant generalizations, including a passage from the setting of probabilities to that of general supermodular functions, and improved bounds for the negative-fugacity singularity of the hard-core model for several lattices.