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: