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)
Algorithmic LLL bad events AE defined on mutually independent random variables X vbl(A):set of variables on which A is defined neighborhood T(A)and inclusive neighborhood I+(A) Assumption: I.We can efficiently sample an independent evaluation of every random variable X∈C. ll.We can efficiently check the violation of every event A E. RandomSolver: sample all X∈C; while 3 a non-violated bad event A∈： resample all XE vbl(A);
Algorithmic LLL bad events A ∈ A defined on mutually independent random variables X ∈ X vbl(A): set of variables on which A is defined neighborhood Γ(A) and inclusive neighborhood Γ+(A) sample all X ∈ X; while ∃ a non-violated bad event A ∈ A: resample all X ∈ vbl(A); RandomSolver: Assumption: I.We can efficiently sample an independent evaluation of every random variable X ∈ X . II. We can efficiently check the violation of every event A ∈ A
bad events A defined on mutually independent random variables X E vbl(A):set of variables on which A is defined neighborhood r(A)and inclusive neighborhood I+(A) RandomSolver: sample all X∈C; while]anon-violated bad event A∈： resample all XE vbl(A); Moser-Tardos 2010: a:A→[0,1) RandomSolver finds values of VA∈A: allX∈X avoiding all A∈ QA Pr[A≤aAΠ(1-aB) within expected B∈T(A) resamples. AEA 1-0A
sample all X ∈ X; while ∃ a non-violated bad event A ∈ A: resample all X ∈ vbl(A); RandomSolver: bad events A ∈ A defined on mutually independent random variables X ∈ X vbl(A): set of variables on which A is defined neighborhood Γ(A) and inclusive neighborhood Γ+(A) Moser-Tardos 2010: RandomSolver finds values of all X ∈ X avoiding all A ∈ A within expected resamples. 8A 2 A : 9↵ : A ! [0, 1) Pr[A] ↵A Y B2(A) (1 ↵B) X A2A ↵A 1 ↵A
bad events A∈几defined on mutually independent random variables X E vbl(A):set of variables on which A is defined neighborhood T(A)and inclusive neighborhood I+(A) RandomSolver: sample all X∈C; while]anon-violated bad event A∈： resample all XE vbl(A); Moser-Tardos 2010: ·HA∈，PrLA]≤p RandomSolver finds values of ep(d+l)≤1 allX∈violating all A∈ where d=maxA IT(A)I within expected I.l/d resamples
Moser-Tardos 2010: RandomSolver finds values of all X ∈ X violating all A ∈ A within expected |A| /d resamples. • ∀ A ∈ A, Pr[A] ≤ p • ep(d + 1) ≤ 1 where d=maxA |Γ(A)| bad events A ∈ A defined on mutually independent random variables X ∈ X vbl(A): set of variables on which A is defined neighborhood Γ(A) and inclusive neighborhood Γ+(A) sample all X ∈ X; while ∃ a non-violated bad event A ∈ A: resample all X ∈ vbl(A); RandomSolver:
k-SAT k-CNF of max degree d with m clauses on n variables RandomSolver: pick a random assignmentx1,x2,...,n; while 3 an unsatisfied clause C: replace variables in C with random values; RandomSolver returns d≤2k-2 三> a satisfying assignment within (e(d+1)s2k) expected O(n km/d)time
k-SAT φ : k-CNF of max degree d with m clauses on n variables RandomSolver returns a satisfying assignment within expected O(n + km/d) time d 2k2 pick a random assignment x1, x2, ... , xn; while ∃ an unsatisfied clause C: replace variables in C with random values; RandomSolver: ( e(d+1)≤2k )
bad events A defined on mutually independent random variables X E vbl(A):set of variables on which A is defined neighborhood r(A)and inclusive neighborhood I+(A) RandomSolver: sample all X∈C; while]anon-violated bad event A∈： resample all XE vbl(A); Moser-Tardos 2010: a:A→[0,1) RandomSolver finds values of VA∈A: allX∈X avoiding all A∈ QA Pr[A≤aAΠ(1-aB) within expected B∈T(A) resamples. AEA 1-0A
sample all X ∈ X; while ∃ a non-violated bad event A ∈ A: resample all X ∈ vbl(A); RandomSolver: bad events A ∈ A defined on mutually independent random variables X ∈ X vbl(A): set of variables on which A is defined neighborhood Γ(A) and inclusive neighborhood Γ+(A) Moser-Tardos 2010: RandomSolver finds values of all X ∈ X avoiding all A ∈ A within expected resamples. 8A 2 A : 9↵ : A ! [0, 1) Pr[A] ↵A Y B2(A) (1 ↵B) X A2A ↵A 1 ↵A
