Loading...
Please wait, while we are loading the content...
CS265/CME309: Randomized Algorithms and Probabilistic Analysis Lecture #12: The Constructive Lovasz Local Lemma (Moser’s Entropic Proof)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Valiant, Gregory |
| Copyright Year | 2019 |
| Abstract | Last class we saw the statement and proof of the existential Lovasz Local Lemma. Today, we will see a constructive (algorithmic) version of the theorem. There has been a long progression of work towards a strong algorithmic version of the theorem over the past thirty years (e.g. [3, 2, 6, 4, 9, 7, 8, 5, 1]). In order to phrase an algorithmic version of the theorem from last class, it will be convenient to slightly restrict the set of events and probability distributions that we will consider. Let V be a finite set of independent random variables, and let A denote a finite set of events that are determined by V . That is, each event A ∈ A maps the set of assignments of V to {0, 1}. Definition 1. Given the set of independent random variables V and set of events A determined by the variables of V , define the relevant variables for an event A ∈ A, denoted vbl(A) ⊂ V to be the smallest subset of variables that determine A. Additionally, for an event A ∈ A, let Γ(A) = {B : vbl(A) ∩ vbl(B) 6= ∅} denote the set of events that share variables with A, and note that A is mutually independent from the set A \ Γ(A). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~valiant/teaching/CS265/lectureNotes/l12.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
