events:A1,A2,...,An d:max degree of dependency graph Lovasz Local Lemma ·Vi,Pr[Al≤p ·ep(d+1)≤1 >l General Lovasz Local Lemma 3c1,.,xn∈[0,1) ∀i,PrA≤(1-x) →- i=1 jvi
events: A1, A2, ... , An d : max degree of dependency graph Lovász Local Lemma • ∀i, Pr[Ai] ≤ p • ep(d + 1) ≤ 1 Pr ⇤ n i=1 Ai ⇥ > 0 General Lovász Local Lemma 9x1,...,xn 2 [0, 1) 8i,Pr[Ai] xi Y j⇠i (1 xj ) Pr " ^ n i=1 Ai # Y n i=1 (1 xi)
Constraint Satisfaction Problem ●variables:x1,x2,,xn∈D(domain) constraints:C1,C2,....Cm ●where C(ri,ri2,)∈{true,false} CSP solution:an assignment of variables satisfying all constraints examples:SAT,graph colorability,... existence:When does a solution exist? search:How to find a solution?
Constraint Satisfaction Problem • variables: x1, x2, ..., xn ∈ D (domain) • constraints: C1, C2, ..., Cm • where • CSP solution: an assignment of variables satisfying all constraints • examples: SAT, graph colorability, ... • existence: When does a solution exist? • search: How to find a solution? Ci(xi1 , xi2 ,...) 2 {true, false}
The Probabilistic Method CSP C1,C2,...Cm defined onx1,x2....xn sampling random values ofx1,x2,..., Bad event Ai:constraint Ci is violated None of the ad troPr The probabilistic method:being good is possible >0 Pr i=1
The Probabilistic Method • sampling random values of x1, x2, ..., xn • Bad event Ai: constraint Ci is violated • None of the bad events occurs with prob: • The probabilistic method: being good is possible Pr" ^ m i Ai # Pr" ^ m i=1 Ai # > 0 CSP C1, C2, ..., Cm defined on x1, x2, ..., xn
mutually independent random variables:XE bad events:A defined on variables in vbl(A):set of variables on which A is defined neighborhood:T(A)={B∈A|B≠A and vbl((A)nvbl(B)≠O} inclusive neighborhood:I+(A)=D(AUA "events that are dependent with A, excluding/including A itself" Lovasz Local Lemma (general) 3a:A→0,1) VA∈A: >AaⅡa-a Pr[A]≤QA Π(1-aB) A∈A B∈T(A) >0
mutually independent random variables: X ∈ X bad events: A ∈ A defined on variables in X vbl(A)⊆ X: set of variables on which A is defined neighborhood: Γ(A) = { B ∈ A | B≠A and vbl(A)∩vbl(B) ≠∅ } inclusive neighborhood: Γ+(A) = Γ(A)∪{ A } “events that are dependent with A, excluding/including A itself” 8A 2 A : Lovász Local Lemma (general) 9↵ : A ! [0, 1) Pr[A] ↵A Y B2(A) (1 ↵B) Pr " ^ A2A A # Y A2A (1 ↵A) > 0
mutually independent random variables:X bad events:A defined on variables in vbl(A):set of variables on which A is defined neighborhood:T(A)={B∈A|B≠A and vbl((A)nvbl(B)≠O} inclusive neighborhood:I+(A)=D(AUA "events that are dependent with A, excluding/including A itself" Lovasz Local Lemma (general) 3a:A→0,1) 3 values of variables in x VA∈A: avoiding all bad events Pr[A]≤aA Π(1-aB) A∈simultaneously, B∈T(A)
∃ values of variables in X avoiding all bad events A ∈ A simultaneously. mutually independent random variables: X ∈ X bad events: A ∈ A defined on variables in X vbl(A)⊆ X: set of variables on which A is defined neighborhood: Γ(A) = { B ∈ A | B≠A and vbl(A)∩vbl(B) ≠∅ } inclusive neighborhood: Γ+(A) = Γ(A)∪{ A } “events that are dependent with A, excluding/including A itself” 8A 2 A : Lovász Local Lemma (general) 9↵ : A ! [0, 1) Pr[A] ↵A Y B2(A) (1 ↵B)