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

 Under construction. 

Lovász Local Lemma

Assume that $A_1,A_2,\dots ,A_n$ are "bad" events. We are looking at the "rare event" that none of these bad events occurs, formally, the event $\underset{i=1}{\overset{n}{\bigwedge }}\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 $A$ is said to be mutually independent of events $B_1,B_2,\dots ,B_k$, if for any disjoint $I^{+},I^{-}\subseteq \{1,2,\dots ,k\}$, it holds that $Pr[A\mid \left(\underset{i\in I^{+}}{\bigwedge }{B}_i\right)\wedge \left(\underset{i\in I^{-}}{\bigwedge }\overline{B_i}\right)]=Pr[A]$.

Given a sequence of events $A_1,A_2,\dots ,A_n$, we use the dependency graph to describe the dependencies between these events.

Definition (dependency graph)

Let $A_1,A_2,\dots ,A_n$ be a sequence of events. A graph $D=(V,E)$ on the set of vertices $V=\{1,2,\dots ,n\}$ is called a dependency graph for the events $A_1,\dots ,A_n$ if for each $i$, $1\le i\le n$, the event $A_i$ is mutually independent of all the events $\{A_j\mid (i,j)\notin E\}$. Furthermore, for each event $A_i$: define $\mathrm{\Gamma }(A_i)=\{A_j\mid (i,j)\in E\}$ as the neighborhood of event $A_i$ in the dependency graph; define ${\mathrm{\Gamma }}^{+}(A_i)=\mathrm{\Gamma }(A_i)\cup \{A_i\}$ as the inclusive neighborhood of $A_i$, i.e. the set of events adjacent to $A_i$ in the dependency graph, including $A_i$ itself.

Example

Let $X_1,X_2,\dots ,X_m$ be a set of mutually independent random variables. Each event $A_i$ is a predicate defined on a number of variables among $X_1,X_2,\dots ,X_m$. Let $v(A_i)$ be the unique smallest set of variables which determine $A_i$. The dependency graph $D=(V,E)$ is defined by

$(i,j)\in E$ iff $v(A_i)\cap v(A_j)\ne \mathrm{\varnothing }$.

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 $A_1,A_2,\dots ,A_n$ be a set of events, and assume that there is a $p\in [0,1)$ such that the followings are satisfied: for all $1\le i\le n$, $Pr[A_i]\le p$; the maximum degree of the dependency graph for the events $A_1,A_2,\dots ,A_n$ is $d$, and $\mathrm{e}p\cdot (d+1)\le 1$. Then $Pr\left[\underset{i=1}{\overset{n}{\bigwedge }}\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 $A_1,A_2,\dots ,A_n$ be a sequence of events. Suppose there exist real numbers $x_1,x_2,\dots ,x_n$ such that $0\le x_i<1$ and for all $1\le i\le n$, $Pr[A_i]\le x_i\prod _{A_j\in \mathrm{\Gamma }(A_i)}(1-x_j)$. Then $Pr\left[\underset{i=1}{\overset{n}{\bigwedge }}\overline{A_i}\right]\ge \prod _{i=1}^n(1-x_i)$.

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

Assume the condition in the symmetric LLL:

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

then it is easy to verify that for all $1\le i\le n$,

$Pr[A_i]\le p\le \frac{1}{\mathrm{e}(d+1)}<\frac{1}{d+1}{(1-\frac{1}{d+1})}^d\le x_i\prod _{A_j\in \mathrm{\Gamma }(A_i)}(1-x_j)$.

Due to the general LLL, we have

$Pr\left[\underset{i=1}{\overset{n}{\bigwedge }}\overline{A_i}\right]\ge \prod _{i=1}^n(1-x_i)={(1-\frac{1}{d+1})}^n>0$.

This proves the symmetric LLL.

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

Lovász Local Lemma (symmetric case, alternative form)

Let $A_1,A_2,\dots ,A_n$ be a set of events, and assume that there is a $p\in [0,1)$ such that the followings are satisfied: for all $1\le i\le n$, $Pr[A_i]\le p$; the maximum degree of the dependency graph for the events $A_1,A_2,\dots ,A_n$ is $d$, and $4pd\le 1$. Then $Pr\left[\underset{i=1}{\overset{n}{\bigwedge }}\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 $k$-SAT

We start by giving the definition of $k$-CNF and $k$-SAT.

Definition (exact-$k$-CNF)

A logic expression $\varphi$ defined on $n$ Boolean variables $x_1,x_2,\dots ,x_n\in \{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e},\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}\}$ is said to be a conjunctive normal form (CNF) if: $\varphi$ can be written as a conjunction(AND) of clauses as $\varphi =C_1\wedge C_2\wedge \cdots \wedge C_m$; each clause $C_i={\ell }_{i_1}\vee {\ell }_{i_2}\vee \cdots \vee {\ell }_{i_k}$ is a disjunction(OR) of literals; each literal ${\ell }_j$ is either a variable $x_i$ or the negation $\mathrm{\neg }{x}_i$ of a variable. We call a CNF formula $k$-CNF, or more precisely an exact-$k$-CNF, if every clause consists of exact $k$ distinct literals.

For example:

$(x_1\vee \mathrm{\neg }{x}_2\vee \mathrm{\neg }{x}_3)\wedge (\mathrm{\neg }{x}_1\vee \mathrm{\neg }{x}_3\vee x_4)\wedge (x_1\vee x_2\vee x_4)\wedge (x_2\vee x_3\vee \mathrm{\neg }{x}_4)$

is a $3$-CNF formula by above definition.

Remark

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

A logic expression $\varphi$ is said to be satisfiable if there is an assignment of values of true or false to the variables $\mathit{x}=(x_1,x_2,\dots ,x_n)$ so that $\varphi (\mathit{x})$ is true. For a CNF $\varphi$, this mean that there is an assignment that satisfies all clauses in $\varphi$ simultaneously.

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

$k$-SAT

Input: a $k$-CNF formula $\varphi$. Determines whether $\varphi$ is satisfiable.

It is well known that $k$-SAT is NP-complete for any $k\ge 3$.

Satisfiability of $k$-CNF

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

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

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

Theorem

Let $\varphi$ be a $k$-CNF formula with maximum degree at most $d$. If $d\le 2^{k-2}$ then $\varphi$ is always satisfiable.

Proof. Let $X_1,X_2,\dots ,X_n$ be Boolean random variables sampled uniformly and independently from $\{\text{true},\text{false}\}$. We are going to show that $\varphi$ is satisfied by this random assignment with positive probability. Due to the probabilistic method, this will prove the existence of a satisfying assignment for $\varphi$. Suppose there are $m$ clauses $C_1,C_2,\dots ,C_m$ in $\varphi$. Let $A_i$ denote the bad event that $C_i$ is not satisfied by the random assignment $X_1,X_2,\dots ,X_n$. Clearly, each $A_i$ is dependent with at most $d$ other $A_j$'s, which means the maximum degree of the dependency graph for $A_1,A_2,\dots ,A_m$ is at most $d$. Recall that in a $k$-CNF $\varphi$, every clause $C_i$ consists of precisely $k$ variable, and $C_i$ is violated by only one assignment among all $2^k$ assignments of the $k$ variables in $C_i$. Therefore, the probability of $C_i$ being violated is $p=Pr[A_i]=2^{-k}$. If $d\le 2^{k-2}$, that is, $4pd\le 1$, then due to Lovasz local lemma (symmetric case, alternative form), it holds that $Pr\left[\underset{i=1}{\overset{m}{\bigwedge }}\overline{A_i}\right]>0$. The existence of satisfying assignment follows by the probabilistic method. $◻$

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 $d\le 2^{k-5}$.

We need the following notations. Given as input a CNF formula $\varphi$:

• let $\mathcal{X}=\{x_1,x_2,\dots ,x_n\}$ be the Boolean variables on which $\varphi$ is defined, and $\mathcal{C}$ the set of clauses in $\varphi$;
• for each clause $C\in \mathcal{C}$, we denote by $\mathsf{v}\mathsf{b}\mathsf{l}(C)\subseteq \mathcal{X}$ the set of variables on which $C$ is defined;
• we also abuse the notation and denote by $\mathrm{\Gamma }(C)=\{D\in \mathcal{C}\mid D\ne C,\mathsf{v}\mathsf{b}\mathsf{l}(C)\cap \mathsf{v}\mathsf{o}\mathsf{l}(D)\ne \varphi \}$ the neighborhood of $C$, i.e. the set of other clauses in $\varphi$ that shares variables with $C$, and ${\mathrm{\Gamma }}^{+}(C)=\mathrm{\Gamma }(C)\cup \{C\}$ the inclusive neighborhood of $C$, i.e. the set of all clauses, including $C$ itself, that share variables with $C$.

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

Solve(CNF $\varphi$)

Pick values of $x_1,x_2\dots ,x_n$ uniformly and independently at random; While there is an unsatisfied clause $C$ in $\varphi$ Fix($C$);

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

Fix(Clause $C$)

Replace the values of variables in $\mathsf{v}\mathsf{b}\mathsf{l}(C)$ with new uniform and independent random values; While there is unsatisfied clause $D\in {\mathrm{\Gamma }}^{+}(C)$ Fix($D$);

It is an amazing discovery that this simple algorithm works well as long as the condition of Lovasz local lemma is satisfied. Here we prove a slightly weaker statement for the convenience of analysis.

Theorem

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

The analysis is based on a technique called entropy compression. This is a very clever idea and may be very different from what you might have seen so far about algorithm analysis. We first give a high-level description of this idea:

• We use $\mathsf{A}\mathsf{l}\mathsf{g}(r,\varphi )$ to abstractly denote an algorithm $\mathsf{A}\mathsf{l}\mathsf{g}$ running on an input $\varphi$ with random bits $r\in \{0,1{\}}^{\ast }$. For an algorithm with no access to the random bits $r$, once the input $\varphi$ is fixed, the behavior of the algorithm as well as its output is deterministic. But for randomized algorithms, the behavior of $\mathsf{A}\mathsf{l}\mathsf{g}(r,\varphi )$ is a random variable even when the input $\varphi$ is fixed.
• Fix an arbitrary (worst-case) input $\varphi$. We try to construct a succinct representation $c$ of the behavior of $\mathsf{A}\mathsf{l}\mathsf{g}(r,\varphi )$ in such a manner that the random bits $r$ can always be fully recovered from this succinct representation $c$. In other words, $\mathsf{A}\mathsf{l}\mathsf{g}(r,\varphi )$ gives an encoding (a 1-1 mapping) of the random bits $r$ to a succinct representation $c$.
• It is a fundamental law that random bits cannot be compressed significantly by any encoding. Therefore if a longer running time of $\mathsf{A}\mathsf{l}\mathsf{g}(r,\varphi )$ would imply that the random bits $r$ can be encoded to a succinct representation $c$ which is much shorter than $r$, then we prove the running time of the algorithm $\mathsf{A}\mathsf{l}\mathsf{g}(r,\varphi )$ cannot be too long.

• A natural way to reach this last contradiction is to have the following situation: As the running time of $\mathsf{A}\mathsf{l}\mathsf{g}(r,\varphi )$ grows, naturally both lengths of random bits $r$ and the succinct representation $c$ of the behavior of $\mathsf{A}\mathsf{l}\mathsf{g}(r,\varphi )$ grow. So if the former grows much faster than the latter as the running time grows, then a large running time may cause the length of $r$ significantly greater than the length of $c$.

---

We now proceed to the analysis of $\text{Solve}(\varphi )$ and prove the above theorem.

From now on we assume that the input instance $\varphi$ is an arbitrarily fixed exact-$k$-CNF formula with maximum degree $d$:

• Let $T$ denote the total number of time the function $\text{Fix}()$ is being called (including both the calls in $\text{Solve}(\varphi )$ and the recursive calls).
• Let $t=min\{T,2^m\}$.

Note that $T$ and $t$ are random variables which depend solely on the random bits used by the algorithm (after the input $\varphi$ being fixed). We are going to show that $t=O(m\log m)$ with high probability, which means $T=O(m\log m)$ with high probability.

The reason we consider $t=min\{T,2^m\}$ is that we are not sure whether $T$ is finite or infinite, so we "truncate" $T$ if it becomes too large. This truncation threshold is quite arbitrary as long as it is significantly greater than $m\log m$.

We start by making the following simple observations:

• A clause $C$ in $\varphi$ will be satisfied after Fix($C$) returned and will remain as being satisfied afterwards.
• At the moment a Fix($C$) being called, the clause $C$ must be unsatisfied.

Proposition

There are at most $m$ top-level callings to Fix(), where $m$ is the total number of clauses in $\varphi$. If a Fix($C$) is being called, the values of variables in $C$ are uniquely determined.