# 高级算法 (Fall 2016)/''Lovász'' Local Lemma

Jump to: navigation, search
 Under construction.


# Lovász Local Lemma

Assume that ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ are "bad" events. We are looking at the "rare event" that none of these bad events occurs, formally, the event ${\displaystyle \bigwedge _{i=1}^{n}{\overline {A_{i}}}}$. How can we guarantee this rare event occurs with positive probability? The Lovász Local Lemma provides an answer to this fundamental question by using the information about the dependencies between the bad events.

## The dependency graph

The notion of mutual independence between an event and a set of events is formally defined as follows.

 Definition (mutual independence) An event ${\displaystyle A}$ is said to be mutually independent of events ${\displaystyle B_{1},B_{2},\ldots ,B_{k}}$, if for any disjoint ${\displaystyle I^{+},I^{-}\subseteq \{1,2,\ldots ,k\}}$, it holds that ${\displaystyle \Pr \left[A\mid \left(\bigwedge _{i\in I^{+}}B_{i}\right)\wedge \left(\bigwedge _{i\in I^{-}}{\overline {B_{i}}}\right)\right]=\Pr[A]}$.

Given a sequence of events ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$, we use the dependency graph to describe the dependencies between these events.

 Definition (dependency graph) Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ be a sequence of events. A graph ${\displaystyle D=(V,E)}$ on the set of vertices ${\displaystyle V=\{1,2,\ldots ,n\}}$ is called a dependency graph for the events ${\displaystyle A_{1},\ldots ,A_{n}}$ if for each ${\displaystyle i}$, ${\displaystyle 1\leq i\leq n}$, the event ${\displaystyle A_{i}}$ is mutually independent of all the events ${\displaystyle \{A_{j}\mid (i,j)\not \in E\}}$. Furthermore, for each event ${\displaystyle A_{i}}$: define ${\displaystyle \Gamma (A_{i})=\{A_{j}\mid (i,j)\in E\}}$ as the neighborhood of event ${\displaystyle A_{i}}$ in the dependency graph; define ${\displaystyle \Gamma ^{+}(A_{i})=\Gamma (A_{i})\cup \{A_{i}\}}$ as the inclusive neighborhood of ${\displaystyle A_{i}}$, i.e. the set of events adjacent to ${\displaystyle A_{i}}$ in the dependency graph, including ${\displaystyle A_{i}}$ itself.
Example
Let ${\displaystyle X_{1},X_{2},\ldots ,X_{m}}$ be a set of mutually independent random variables. Each event ${\displaystyle A_{i}}$ is a predicate defined on a number of variables among ${\displaystyle X_{1},X_{2},\ldots ,X_{m}}$. Let ${\displaystyle v(A_{i})}$ be the unique smallest set of variables which determine ${\displaystyle A_{i}}$. The dependency graph ${\displaystyle D=(V,E)}$ is defined by
${\displaystyle (i,j)\in E}$ iff ${\displaystyle v(A_{i})\cap v(A_{j})\neq \emptyset }$.

## The local lemma

The following lemma, known as the Lovász local lemma, first proved by Erdős and Lovász in 1975, is an extremely powerful tool, as it supplies a way for dealing with rare events.

 Lovász Local Lemma (symmetric case) Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ be a set of events, and assume that there is a ${\displaystyle p\in [0,1)}$ such that the followings are satisfied: for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq p}$; the maximum degree of the dependency graph for the events ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ is ${\displaystyle d}$, and ${\displaystyle \mathrm {e} p\cdot (d+1)\leq 1}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]>0}$.

The following is a general asymmetric version of the local lemma. This generalization is due to Spencer.

 Lovász Local Lemma (general case) Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ be a sequence of events. Suppose there exist real numbers ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ such that ${\displaystyle 0\leq x_{i}<1}$ and for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq x_{i}\prod _{A_{j}\in \Gamma (A_{i})}(1-x_{j})}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]\geq \prod _{i=1}^{n}(1-x_{i})}$.

To see that the general LLL implies symmetric LLL, we set ${\displaystyle x_{i}={\frac {1}{d+1}}}$ for all ${\displaystyle i=1,2,\ldots ,n}$. Then we have ${\displaystyle \left(1-{\frac {1}{d+1}}\right)^{d}>{\frac {1}{\mathrm {e} }}}$.

Assume the condition in the symmetric LLL:

1. for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq p}$;
2. ${\displaystyle \mathrm {e} p\cdot (d+1)\leq 1}$;

then it is easy to verify that for all ${\displaystyle 1\leq i\leq n}$,

${\displaystyle \Pr[A_{i}]\leq p\leq {\frac {1}{\mathrm {e} (d+1)}}<{\frac {1}{d+1}}\left(1-{\frac {1}{d+1}}\right)^{d}\leq x_{i}\prod _{A_{j}\in \Gamma (A_{i})}(1-x_{j})}$.

Due to the general LLL, we have

${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]\geq \prod _{i=1}^{n}(1-x_{i})=\left(1-{\frac {1}{d+1}}\right)^{n}>0}$.

This proves the symmetric LLL.

Alternatively, by setting ${\displaystyle x_{i}={\frac {1}{d}}}$ and assuming without loss of generality that the maximum degree of the dependency graph has ${\displaystyle d\geq 2}$, we can have another symmetric version of the local lemma.

 Lovász Local Lemma (symmetric case, alternative form) Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ be a set of events, and assume that there is a ${\displaystyle p\in [0,1)}$ such that the followings are satisfied: for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq p}$; the maximum degree of the dependency graph for the events ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ is ${\displaystyle d}$, and ${\displaystyle 4pd\leq 1}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]>0}$.

The original proof of the Lovász Local Lemma is by induction. See this note for the original non-constructive proof of Lovász Local Lemma.

# Random Search for ${\displaystyle k}$-SAT

We start by giving the definition of ${\displaystyle k}$-CNF and ${\displaystyle k}$-SAT.

 Definition (exact-${\displaystyle k}$-CNF) A logic expression ${\displaystyle \phi }$ defined on ${\displaystyle n}$ Boolean variables ${\displaystyle x_{1},x_{2},\ldots ,x_{n}\in \{\mathrm {true} ,\mathrm {false} \}}$ is said to be a conjunctive normal form (CNF) if: ${\displaystyle \phi }$ can be written as a conjunction(AND) of clauses as ${\displaystyle \phi =C_{1}\wedge C_{2}\wedge \cdots \wedge C_{m}}$; each clause ${\displaystyle C_{i}=\ell _{i_{1}}\vee \ell _{i_{2}}\vee \cdots \vee \ell _{i_{k}}}$ is a disjunction(OR) of literals; each literal ${\displaystyle \ell _{j}}$ is either a variable ${\displaystyle x_{i}}$ or the negation ${\displaystyle \neg x_{i}}$ of a variable. We call a CNF formula ${\displaystyle k}$-CNF, or more precisely an exact-${\displaystyle k}$-CNF, if every clause consists of exact ${\displaystyle k}$ distinct literals.

For example:

${\displaystyle (x_{1}\vee \neg x_{2}\vee \neg x_{3})\wedge (\neg x_{1}\vee \neg x_{3}\vee x_{4})\wedge (x_{1}\vee x_{2}\vee x_{4})\wedge (x_{2}\vee x_{3}\vee \neg x_{4})}$

is a ${\displaystyle 3}$-CNF formula by above definition.

Remark
The notion of ${\displaystyle k}$-CNF defined here is slightly more restrictive than the standard definition of ${\displaystyle k}$-CNF, where each clause consists of at most ${\displaystyle k}$ variables. See here for a discussion of the subtle differences between these two definitions.

A logic expression ${\displaystyle \phi }$ is said to be satisfiable if there is an assignment of values of true or false to the variables ${\displaystyle {\boldsymbol {x}}=(x_{1},x_{2},\ldots ,x_{n})}$ so that ${\displaystyle \phi ({\boldsymbol {x}})}$ is true. For a CNF ${\displaystyle \phi }$, this mean that there is an assignment that satisfies all clauses in ${\displaystyle \phi }$ simultaneously.

The ${\displaystyle k}$-satisfiability (${\displaystyle k}$-SAT) problem is that given as input a ${\displaystyle k}$-CNF formula ${\displaystyle \phi }$ decide whether ${\displaystyle \phi }$ is satisfiable.

 ${\displaystyle k}$-SAT Input: a ${\displaystyle k}$-CNF formula ${\displaystyle \phi }$. Determines whether ${\displaystyle \phi }$ is satisfiable.

It is well known that ${\displaystyle k}$-SAT is NP-complete for any ${\displaystyle k\geq 3}$.

## Satisfiability of ${\displaystyle k}$-CNF

As in the Lovasz local lemma, we consider the dependencies between clauses in a CNF formula.

We say that a CNF formula ${\displaystyle \phi }$ has maximum degree at most ${\displaystyle d}$ if every clause in ${\displaystyle \phi }$ shares variables with at most ${\displaystyle d}$ other clauses in ${\displaystyle \phi }$.

By the Lovasz local lemma, we almost immediately have the following theorem for the satisfiability of ${\displaystyle k}$-CNF with bounded degree.

 Theorem Let ${\displaystyle \phi }$ be a ${\displaystyle k}$-CNF formula with maximum degree at most ${\displaystyle d}$. If ${\displaystyle d\leq 2^{k-2}}$ then ${\displaystyle \phi }$ is always satisfiable.
Proof.
 Let ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ be Boolean random variables sampled uniformly and independently from ${\displaystyle \{{\text{true}},{\text{false}}\}}$. We are going to show that ${\displaystyle \phi }$ is satisfied by this random assignment with positive probability. Due to the probabilistic method, this will prove the existence of a satisfying assignment for ${\displaystyle \phi }$. Suppose there are ${\displaystyle m}$ clauses ${\displaystyle C_{1},C_{2},\ldots ,C_{m}}$ in ${\displaystyle \phi }$. Let ${\displaystyle A_{i}}$ denote the bad event that ${\displaystyle C_{i}}$ is not satisfied by the random assignment ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$. Clearly, each ${\displaystyle A_{i}}$ is dependent with at most ${\displaystyle d}$ other ${\displaystyle A_{j}}$'s, which means the maximum degree of the dependency graph for ${\displaystyle A_{1},A_{2},\ldots ,A_{m}}$ is at most ${\displaystyle d}$. Recall that in a ${\displaystyle k}$-CNF ${\displaystyle \phi }$, every clause ${\displaystyle C_{i}}$ consists of precisely ${\displaystyle k}$ variable, and ${\displaystyle C_{i}}$ is violated by only one assignment among all ${\displaystyle 2^{k}}$ assignments of the ${\displaystyle k}$ variables in ${\displaystyle C_{i}}$. Therefore, the probability of ${\displaystyle C_{i}}$ being violated is ${\displaystyle p=\Pr[A_{i}]=2^{-k}}$. If ${\displaystyle d\leq 2^{k-2}}$, that is, ${\displaystyle 4pd\leq 1}$, then due to Lovasz local lemma (symmetric case, alternative form), it holds that ${\displaystyle \Pr \left[\bigwedge _{i=1}^{m}{\overline {A_{i}}}\right]>0}$. The existence of satisfying assignment follows by the probabilistic method.
${\displaystyle \square }$

## Moser's recursive fix algorithm

The above theorem basically says that for a CNF if every individual clause is easy to satisfy and is dependent with few other clauses then the CNF should be always satisfiable. However, the theorem only states the existence of a satisfying solution, but does not gives a way to find such solution.

In 2009, Moser gave a very simple randomized algorithm which efficiently finds a satisfying assignment with high probability under the condition ${\displaystyle d\leq 2^{k-5}}$.

We need the following notations. Given as input a CNF formula ${\displaystyle \phi }$:

• Let ${\displaystyle {\mathcal {X}}=\{x_{1},x_{2},\ldots ,x_{n}\}}$ be the set of Boolean variables on which ${\displaystyle \phi }$ is defined.
• For each clause ${\displaystyle C}$ in ${\displaystyle \phi }$, we denote by ${\displaystyle {\mathsf {vbl}}(C)\subseteq {\mathcal {X}}}$ the set of variables on which ${\displaystyle C}$ is defined.
• We also abuse the notation and denote by ${\displaystyle \Gamma (C)=\{{\text{clause }}D{\text{ in }}\phi \mid D\neq C,{\mathsf {vbl}}(C)\cap {\mathsf {vbl}}(D)\neq \phi \}}$ the neighborhood of ${\displaystyle C}$, i.e. the set of other clauses in ${\displaystyle \phi }$ that shares variables with ${\displaystyle C}$, and ${\displaystyle \Gamma ^{+}(C)=\Gamma (C)\cup \{C\}}$ the inclusive neighborhood of ${\displaystyle C}$, i.e. the set of all clauses, including ${\displaystyle C}$ itself, that share variables with ${\displaystyle C}$.

The algorithm consists of two functions: the main function Solve() and a recursive sub-routine Fix().

 Solve(CNF ${\displaystyle \phi }$) Pick values of ${\displaystyle x_{1},x_{2}\ldots ,x_{n}}$ uniformly and independently at random; while there is an unsatisfied clause ${\displaystyle C}$ in ${\displaystyle \phi }$ Fix(${\displaystyle C}$);

The sub-routine Fix() is a recursive procedure:

 Fix(Clause ${\displaystyle C}$) Replace the values of variables in ${\displaystyle {\mathsf {vbl}}(C)}$ with uniform and independent random values; while there is unsatisfied clause ${\displaystyle D\in \Gamma ^{+}(C)}$ Fix(${\displaystyle D}$);

It is quite amazing to see that this simple algorithm works very well.

 Theorem Let ${\displaystyle \phi }$ be a ${\displaystyle k}$-CNF formula with maximum degree at most ${\displaystyle d}$. There is a universal constant ${\displaystyle c>0}$, such that if ${\displaystyle d<2^{k-c}}$ then the algorithm Solve(${\displaystyle \phi }$) finds a satisfying assignment for ${\displaystyle \phi }$ in time ${\displaystyle O(n+km\log m)}$ with high probability.

# Constructive Proof of General LLL

• ${\displaystyle {\mathcal {X}}}$ is a set of mutually independent random variables.
• ${\displaystyle {\mathcal {A}}}$ is a set of events defined on variables in ${\displaystyle {\mathcal {X}}}$, where each ${\displaystyle A\in {\mathcal {A}}}$ is a predicate defined on a subset of random variables in ${\displaystyle {\mathcal {X}}}$.
• For each ${\displaystyle A\in {\mathcal {A}}}$, denote by ${\displaystyle {\mathsf {vbl}}(A)}$ the set of variables on which ${\displaystyle A}$ is defined.
• For each ${\displaystyle A\in {\mathcal {A}}}$, the neighborhood of ${\displaystyle A}$, denoted by ${\displaystyle \Gamma (A)}$, is defined as
${\displaystyle \Gamma (A)=\{B\in {\mathcal {A}}\mid B\neq A,{\mathsf {vbl}}(A)\cap {\mathsf {vbl}}(B)\neq \emptyset \}}$;
• and let ${\displaystyle \Gamma ^{+}(A)=\Gamma (A)\cup \{A\}}$ be the inclusive neighborhood of ${\displaystyle A}$.

We still interpret the events in ${\displaystyle {\mathcal {A}}}$ as a series of bad events, and we want to make sure it is possible to avoid the occurrences of all bad events in ${\displaystyle {\mathcal {A}}}$ simultaneously. Furthermore, we want to give an algorithm which can efficiently find an evaluation of the random variables in ${\displaystyle {\mathcal {X}}}$ to make none of the bad events in ${\displaystyle {\mathcal {A}}}$ occur.

## The Moser-Tardos random solver

We make the following assumptions:

• It is efficient to draw independent samples for every random variable ${\displaystyle X\in {\mathcal {X}}}$ according to its distribution.
• It is efficient to evaluate whether ${\displaystyle A}$ occurs on an evaluation of random variables in ${\displaystyle {\mathsf {vbl}}(A)}$.
 Moser-Tardos Algorithm Sample all ${\displaystyle X\in {\mathcal {X}}}$ independently; while there is a bad event ${\displaystyle A\in {\mathcal {A}}}$ that occurs resample all ${\displaystyle X\in {\mathsf {vbl}}(A)}$;
 Theorem (Moser-Tardos 2010) If there is an ${\displaystyle \alpha :{\mathcal {A}}\to [0,1)}$ such that for every ${\displaystyle A\in {\mathcal {A}}}$ ${\displaystyle \Pr[A]\leq \alpha (A)\prod _{B\in \Gamma (A)}(1-\alpha (B))}$, then the Moser-Tardos algorithm returns an evaluation of random variables in ${\displaystyle {\mathcal {X}}}$ satisfying ${\displaystyle \bigwedge _{A\in {\mathcal {A}}}{\overline {A}}}$ using at most ${\displaystyle \sum _{A\in {\mathcal {A}}}{\frac {\alpha (A)}{1-\alpha (A)}}}$ resamples in expectation.