Limited Dependency 。k-CNF:Φ=C1AC2N…∧Cm k variables Φ=(x1Vx2Vx3)∧(x1Vx2Vx4)Λ(x3V74Vx5) Dependency degree d: each clause intersects d other clauses uniform random1,...,[T,F),each clause is violated w.p.2-k (union bound)m2k<1 (local union bound?)d2 Pr[no clause is violated ]>0 LLL)e(d+1)2k≤1丿 4d2-k≤1• -CNF: • uniform random , each clause is violated w.p. k Φ = C1 ∧ C2 ∧ ⋯ ∧ Cm Φ = (x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x3 ∨ ¬x4 ∨ ¬x5) x1, …, xn ∈ {𝚃, 𝙵} 2−k Limited Dependency k variables ⟹ Pr[ no clause is violated ] > 0 (union bound) m2−k < 1 } (“local” union bound?) d2−k < 1 (LLL) e(d + 1)2−k ≤ 1 Dependency degree : each clause intersects other clauses d ≤ d 4d2−k ≤ 1