高级算法 (Fall 2016)/''Lovász'' Local Lemma
Under construction.
Lovász Local Lemma
Assume that are "bad" events. We are looking at the "rare event" that none of these bad events occurs, formally, the event . 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 is said to be mutually independent of events , if for any disjoint , it holds that
- .
- An event is said to be mutually independent of events , if for any disjoint , it holds that
Given a sequence of events , we use the dependency graph to describe the dependencies between these events.
Definition (dependency graph) - Let be a sequence of events. A graph on the set of vertices is called a dependency graph for the events if for each , , the event is mutually independent of all the events .
- Furthermore, for each event :
- define as the neighborhood of event in the dependency graph;
- define as the inclusive neighborhood of , i.e. the set of events adjacent to in the dependency graph, including itself.
- Example
- Let be a set of mutually independent random variables. Each event is a predicate defined on a number of variables among . Let be the unique smallest set of variables which determine . The dependency graph is defined by
- iff .
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 be a set of events, and assume that there is a such that the followings are satisfied:
- for all , ;
- the maximum degree of the dependency graph for the events is , and
- .
- Then
- .
- Let be a set of events, and assume that there is a such that the followings are satisfied:
The following is a general asymmetric version of the local lemma. This generalization is due to Spencer.
Lovász Local Lemma (general case) - Let be a sequence of events. Suppose there exist real numbers such that and for all ,
- .
- Then
- .
- Let be a sequence of events. Suppose there exist real numbers such that and for all ,
To see that the general LLL implies symmetric LLL, we set for all . Then we have .
Assume the condition in the symmetric LLL:
- for all , ;
- ;
then it is easy to verify that for all ,
- .
Due to the general LLL, we have
- .
This proves the symmetric LLL.
Alternatively, by setting and assuming without loss of generality that the maximum degree of the dependency graph has , we can have another symmetric version of the local lemma.
Lovász Local Lemma (symmetric case, alternative form) - Let be a set of events, and assume that there is a such that the followings are satisfied:
- for all , ;
- the maximum degree of the dependency graph for the events is , and
- .
- Then
- .
- Let be a set of events, and assume that there is a such that the followings are satisfied:
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 -SAT
We start by giving the definition of -CNF and -SAT.
Definition (exact--CNF) - A logic expression defined on Boolean variables is said to be a conjunctive normal form (CNF) if:
- can be written as a conjunction(AND) of clauses as ;
- each clause is a disjunction(OR) of literals;
- each literal is either a variable or the negation of a variable.
- We call a CNF formula -CNF, or more precisely an exact--CNF, if every clause consists of exact distinct literals.
- A logic expression defined on Boolean variables is said to be a conjunctive normal form (CNF) if:
For example:
is a -CNF formula by above definition.
- Remark
- The notion of -CNF defined here is slightly more restrictive than the standard definition of -CNF, where each clause consists of at most variables. See here for a discussion of the subtle differences between these two definitions.
A logic expression is said to be satisfiable if there is an assignment of values of true or false to the variables so that is true. For a CNF , this mean that there is an assignment that satisfies all clauses in simultaneously.
The -satisfiability (-SAT) problem is that given as input a -CNF formula decide whether is satisfiable.
-SAT - Input: a -CNF formula .
- Determines whether is satisfiable.
It is well known that -SAT is NP-complete for any .
Satisfiability of -CNF
As in the Lovasz local lemma, we consider the dependencies between clauses in a CNF formula.
We say that a CNF formula has maximum degree at most if every clause in shares variables with at most other clauses in .
By the Lovasz local lemma, we almost immediately have the following theorem for the satisfiability of -CNF with bounded degree.
Theorem - Let be a -CNF formula with maximum degree at most . If then is always satisfiable.
Proof. Let be Boolean random variables sampled uniformly and independently from . We are going to show that is satisfied by this random assignment with positive probability. Due to the probabilistic method, this will prove the existence of a satisfying assignment for .
Suppose there are clauses in . Let denote the bad event that is not satisfied by the random assignment . Clearly, each is dependent with at most other 's, which means the maximum degree of the dependency graph for is at most .
Recall that in a -CNF , every clause consists of precisely variable, and is violated by only one assignment among all assignments of the variables in . Therefore, the probability of being violated is .
If , that is, , then due to Lovasz local lemma (symmetric case, alternative form), it holds that
- .
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 .
We need the following notations. Given as input a CNF formula :
- Let be the set of Boolean variables on which is defined.
- For each clause in , we denote by the set of variables on which is defined.
- We also abuse the notation and denote by the neighborhood of , i.e. the set of other clauses in that shares variables with , and the inclusive neighborhood of , i.e. the set of all clauses, including itself, that share variables with .
The algorithm consists of two functions: the main function Solve() and a recursive sub-routine Fix().
Solve(CNF ) - Pick values of uniformly and independently at random;
- while there is an unsatisfied clause in
- Fix();
The sub-routine Fix() is a recursive procedure:
Fix(Clause ) - Replace the values of variables in with uniform and independent random values;
- while there is unsatisfied clause
- Fix();
It is quite amazing to see that this simple algorithm works very well.
Theorem - Let be a -CNF formula with maximum degree at most .
- There is a universal constant , such that if then the algorithm Solve() finds a satisfying assignment for in time with high probability.
Analysis of Moser's algorithm by entropy compression
Constructive Proof of General LLL
- is a set of mutually independent random variables.
- is a set of events defined on variables in , where each is a predicate defined on a subset of random variables in .
- For each , denote by the set of variables on which is defined.
- For each , the neighborhood of , denoted by , is defined as
- ;
- and let be the inclusive neighborhood of .
We still interpret the events in as a series of bad events, and we want to make sure it is possible to avoid the occurrences of all bad events in simultaneously. Furthermore, we want to give an algorithm which can efficiently find an evaluation of the random variables in to make none of the bad events in occur.
The Moser-Tardos random solver
We make the following assumptions:
- It is efficient to draw independent samples for every random variable according to its distribution.
- It is efficient to evaluate whether occurs on an evaluation of random variables in .
Moser-Tardos Algorithm - Sample all independently;
- while there is a bad event that occurs
- resample all ;
Theorem (Moser-Tardos 2010) - If there is an such that for every
- ,
- then the Moser-Tardos algorithm returns an evaluation of random variables in satisfying using at most resamples in expectation.
- If there is an such that for every