南京大学：《计算理论之美》课程教学资源（课件讲稿）Cluster expansion lemma

Cluster expansion lemma 中科院计算所量子计算与算法理论实验室 何昆 hekun@ict.ac.cn https://theory.ict.ac.cn/cn/ https://theory.ict.ac.cn/en/members/hekun/

中科院计算所 量子计算与算法理论实验室 何 昆 hekun@ict.ac.cn Cluster expansion lemma https://theory.ict.ac.cn/en/members/hekun/ https://theory.ict.ac.cn/cn/

m bad event:A{A1,A2,...,Am} Lovasz Local Lemma (asymmetric version): 3a:A→[0,1) A∈A:Pr[A≤aAnI(1-aa） →公 II(1-@a) A∈A BEr(A) neighborhood:r(A)[BEA I A and B are adjacent in the dependency graph} Example: A2 A1(X1,X4) A A4(X4) A3 A2(X1,X2) A5 A5(X3) A4 A3(X2,X3) dependency graph X1,X2,X3,X4 (max degree d) are mutually independent

m bad event: 𝒜 ≜ {𝐴1, 𝐴2, … , 𝐴𝑚} 𝐴1(𝑋1, 𝑋4) 𝐴2(𝑋1, 𝑋2) 𝐴3(𝑋2, 𝑋3) 𝐴4(𝑋4) 𝐴5(𝑋3) 𝑋1, 𝑋2, 𝑋3, 𝑋4 are mutually independent dependency graph Example: (max degree d) Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝛼𝐴 ∏ 𝐵∈Γ(𝐴) (1 − 𝛼𝐵) ∃𝛼: 𝒜 → [0,1) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 (1 − 𝛼𝐴) neighborhood: Γ(𝐴) ≜ {𝐵 ∈ 𝒜 ∣ 𝐴 and 𝐵 are adjacent in the dependency graph}

Lovasz Local Lemma (asymmetric version): 3:A→[0,1) HA∈A:Pr[A]≤aAI(1-aB) (1-A) AEA BEr(A) VA∈凡：A=1-aA A HA CLA三1+LA 1 (1-B)= 1十HA BETCA) 1+B =LA BEr(A) BEr+(A 1+B HA HA IIBEr+(A)(1+B)EIsr+(A)IIBEI B Example: 。+(A)={A1=A,A2} ·ΠBer+A(1+B)=1·1+A1·1+1·A2+A1·A2 inclusive neighborhood: T+(A)会T(A)U{A

Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝛼𝐴 ∏ 𝐵∈Γ(𝐴) (1 − 𝛼𝐵) ∃𝛼: 𝒜 → [0,1) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 (1 − 𝛼𝐴) ∀𝐴 ∈ 𝒜: 𝜇𝐴 = 𝛼𝐴 1 − 𝛼𝐴 𝛼𝐴 = 𝜇𝐴 1 + 𝜇𝐴 𝛼𝐴 ෑ 𝐵∈Γ 𝐴 1 − 𝛼𝐵 = 𝜇𝐴 1 + 𝜇𝐴 ෑ 𝐵∈Γ 𝐴 1 1 + 𝜇𝐵 = 𝜇𝐴 ෑ 𝐵∈Γ+ 𝐴 1 1 + 𝜇𝐵 = 𝜇𝐴 ∏𝐵∈Γ+ 𝐴 1 + 𝜇𝐵 = 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Γ + inclusive neighborhood: (𝐴) ≜ Γ(𝐴) ∪ {𝐴} • Γ + 𝐴 = {𝐴1 = 𝐴, 𝐴2} • ∏𝐵∈Γ+ 𝐴 1 + 𝜇𝐵 = 1 ⋅ 1 + 𝜇𝐴1 ⋅ 1 + 1 ⋅ 𝜇𝐴2 + 𝜇𝐴1 ⋅ 𝜇𝐴2 Example:

Lovasz Local Lemma (asymmetric version): m 3a:A→[0,1) AeA:Pr[A≤aAIa-g) BET(A) 思- VA∈L:a=1-aA A MA A= 1+uA A1-ae=1+ar LA一 1 BEr(A) 1+B =WA 1+B BEr+(A) HA HA TIBEr+(A(1+B)EIsr+(A)IIBeUB Lovasz Local Lemma (asymmetric version): 3:A→(0，+∞) AetPiWsZerileae inclusive neighborhood: +(A)会T(A)U{A

Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝛼𝐴 ∏ 𝐵∈Γ(𝐴) (1 − 𝛼𝐵) ∃𝛼: 𝒜 → [0,1) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 (1 − 𝛼𝐴) ∀𝐴 ∈ 𝒜: 𝜇𝐴 = 𝛼𝐴 1 − 𝛼𝐴 𝛼𝐴 = 𝜇𝐴 1 + 𝜇𝐴 𝛼𝐴 ෑ 𝐵∈Γ 𝐴 1 − 𝛼𝐵 = 𝜇𝐴 1 + 𝜇𝐴 ෑ 𝐵∈Γ 𝐴 1 1 + 𝜇𝐵 = 𝜇𝐴 ෑ 𝐵∈Γ+ 𝐴 1 1 + 𝜇𝐵 = 𝜇𝐴 ∏𝐵∈Γ+ 𝐴 1 + 𝜇𝐵 = 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∃𝜇: 𝒜 → (0, +∞) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 1 1 + 𝜇𝐴 Γ + inclusive neighborhood: (𝐴) ≜ Γ(𝐴) ∪ {𝐴}

Lovasz Local Lemma (asymmetric version): m 3:A→[0,1) HA∈A:Pr[A]≤aAI(1-aB) AEA】 BEr(A) VA∈凡：A=1-aA XA HA CLA三1十LA 1 1 (1-aB)= 1十HA BET(A) 1+B =LA BEr(A) BEr+(A) 1+B HA HA ΠBer+A(1+4B) EIsr+(A TIBEI HB Lovasz Local Lemma (asymmetric version): 3:A→(0，+∞) VA内s2iee A inclusive neighborhood: T+(A)兰T(A)U{A

Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝛼𝐴 ∏ 𝐵∈Γ(𝐴) (1 − 𝛼𝐵) ∃𝛼: 𝒜 → [0,1) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 (1 − 𝛼𝐴) ∀𝐴 ∈ 𝒜: 𝜇𝐴 = 𝛼𝐴 1 − 𝛼𝐴 𝛼𝐴 = 𝜇𝐴 1 + 𝜇𝐴 𝛼𝐴 ෑ 𝐵∈Γ 𝐴 1 − 𝛼𝐵 = 𝜇𝐴 1 + 𝜇𝐴 ෑ 𝐵∈Γ 𝐴 1 1 + 𝜇𝐵 = 𝜇𝐴 ෑ 𝐵∈Γ+ 𝐴 1 1 + 𝜇𝐵 = 𝜇𝐴 ∏𝐵∈Γ+ 𝐴 1 + 𝜇𝐵 = 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∃𝜇: 𝒜 → (0, +∞) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 1 1 + 𝜇𝐴 Γ + inclusive neighborhood: (𝐴) ≜ Γ(𝐴) ∪ {𝐴}

m bad event:AA1,A2,...Am} Lovasz Local Lemma (asymmetric version): 3u:A→(0，+o) m aet.rW≤Er oP neighborhood:T(A)B EA I A and B are adjacent in the dependency graph} inclusive neighborhood:r+(A)r(A)U{A} Cluster Expansion Lovasz Local Lemma (Bissacot et.al.2009): 3:A→(0，+∞) VA∈A:Pr[A≤Indep.I+le A →公

m bad event: 𝒜 ≜ {𝐴1, 𝐴2, … , 𝐴𝑚} Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∃𝜇: 𝒜 → (0, +∞) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 1 1 + 𝜇𝐴 Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ෑ 𝐴∈𝒜 1 1 + 𝜇𝐴 Cluster Expansion Lovász Local Lemma (Bissacot et. al. 2009): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝐼𝑛𝑑𝑒𝑝. 𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∃𝜇: 𝒜 → (0, +∞) neighborhood: Γ(𝐴) ≜ {𝐵 ∈ 𝒜 ∣ 𝐴 and 𝐵 are adjacent in the dependency graph} Γ + inclusive neighborhood: (𝐴) ≜ Γ(𝐴) ∪ {𝐴}

LLL condition:u:A→(0，+o) VS A:as PrInAEsA], VA∈A:PrA]≤nep1Er+Tine ko HA 4s ΣΠa Indep.IES AET Example: ·9A=Pr[n4eAA ·hrtA=∑inaep.Ier+ATIBEI HB ·A=儿A-1 Pr[A≤4-1 r+(A)

LLL condition: ∃𝜇: 𝒜 → (0, +∞) ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝑖𝑛𝑑𝑒𝑝. 𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∀𝑆 ⊆ 𝒜: 𝑞෬𝑆 ≜ Pr[⋂𝐴∈𝑆𝐴ҧ], 𝜇𝑆 ≜ ෍ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 • 𝑞 ෬ 𝒜 = Pr[⋂𝐴∈𝒜𝐴ҧ] • • • 𝜇Γ +(𝐴) = σ𝑖𝑛𝑑𝑒𝑝. 𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Example: Pr[𝐴] ≤ 𝜇{𝐴}−1 𝜇Γ+(𝐴) 𝜇𝐴 = 𝜇{𝐴} − 1

LLL condition:]:A→(0，+oo) SSA:is≌Pr[n4esA, HA∈A:Pr[A]≤ MA 4s兰 T+(A) ∑Ia Indep.ICS AEI Example: ·9.A=Pr[nAEAA] ·hrt(A=∑indep.Isr+AIIBEIB ·4A=A-1 ·Pr[A≤HA- r+(A)

LLL condition: ∃𝜇: 𝒜 → (0, +∞) ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 𝜇Γ+(𝐴) ∀𝑆 ⊆ 𝒜: 𝑞෬𝑆 ≜ Pr[⋂𝐴∈𝑆𝐴ҧ], 𝜇𝑆 ≜ ෍ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 • 𝑞 ෬ 𝒜 = Pr[⋂𝐴∈𝒜𝐴ҧ] • • • 𝜇Γ +(𝐴) = σ𝑖𝑛𝑑𝑒𝑝. 𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Example: Pr[𝐴] ≤ 𝜇{𝐴}−1 𝜇Γ+(𝐴) 𝜇𝐴 = 𝜇{𝐴} − 1

LLL condition:]:A→(0，+o) VS A:asPr[nAESA], VA∈A:Pr[A]≤ A 4s T+(A) ΣΠa Indep.IES Ael Recursive bounds: S∈A,B∈S: AB)≤9s+Pr(B)ar+(B) S∈A,BtS: sUB)≥s+Pr(B)sUr+(B) is Pr[nAES\(B)A]-Pr[B ANAES\(B)A] ≥PrInAeS\个-Pr[BANAES\+(aA BASB ≥Pr[nAee-Pr]Pr[nAer+e可 S(B) =ds\(B)-Pr(B)qs\r+(B)

𝑞 ෬ 𝑆 = Pr ⋂𝐴∈𝑆∖ 𝐵 𝐴ҧ − Pr 𝐵 ∧ ⋂𝐴∈𝑆∖ 𝐵 𝐴ҧ ∀𝑆 ⊆ 𝒜: 𝑞෬𝑆 ≜ Pr[⋂𝐴∈𝑆𝐴ҧ], 𝜇𝑆 ≜ ෍ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 Recursive bounds: 𝑞෬𝑆∖ 𝐵 ≤ 𝑞෬𝑆 + Pr 𝐵 𝑞෬𝑆∖Γ + 𝐵 𝜇𝑆∪{𝐵} ≥ 𝜇𝑆 + Pr(𝐵) 𝜇𝑆∪Γ +(𝐵) = 𝑞 ෬ 𝑆∖ 𝐵 − Pr(𝐵)𝑞 ෬ 𝑆∖Γ +(𝐵) ≥ Pr ⋂𝐴∈𝑆∖ 𝐵 𝐴ҧ − Pr 𝐵 ∧ ⋂𝐴∈𝑆∖Γ +(𝐵)𝐴ҧ ≥ Pr ⋂𝐴∈𝑆∖ 𝐵 𝐴ҧ − Pr 𝐵 Pr ⋂𝐴∈𝑆∖Γ +(𝐵)𝐴ҧ 𝐵 ∧ 𝑆 ∖ 𝐵 𝑆ҧ 𝑆 ∖ 𝐵 ∀𝑆 ⊆ 𝒜, 𝐵 ∉ 𝑆: LLL condition: ∃𝜇: 𝒜 → (0, +∞) ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 𝜇Γ+(𝐴) ∀𝑆 ⊆ 𝒜, 𝐵 ∈ 𝑆:

LLL condition::3:A→(0，+∞) S∈A:as±Pr[n4esA, HA∈A:Pr[A]≤ MA s合 T+(A) ∑Ia Indep.IcSA∈l Recursive bounds: S∈A,BeS: 4s\(B)4s+Pr(B)qs\r+(B) VS∈A,BtS: USU(B)2 us +Pr(B)usur+(B) 4ua=∑+∑Πa I∈S Indep.IsSA∈l BEIndep.IESUB AEI B∈I∈SU{B} Indep.I∈SU{B}

∀𝑆 ⊆ 𝒜: 𝑞෬𝑆 ≜ Pr[⋂𝐴∈𝑆𝐴ҧ], 𝜇𝑆 ≜ ෍ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 Recursive bounds: 𝑞෬𝑆∖ 𝐵 ≤ 𝑞෬𝑆 + Pr 𝐵 𝑞෬𝑆∖Γ + 𝐵 𝜇𝑆∪{𝐵} ≥ 𝜇𝑆 + Pr(𝐵) 𝜇𝑆∪Γ + ∀𝑆 ⊆ 𝒜 (𝐵) , 𝐵 ∉ 𝑆: 𝜇𝑆∪{𝐵} = ෍ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 + ෍ 𝐵∈𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆∪𝐵 ෑ 𝐴∈𝐼 𝜇𝐴 LLL condition: ∃𝜇: 𝒜 → (0, +∞) ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 𝜇Γ+(𝐴) ∀𝑆 ⊆ 𝒜, 𝐵 ∈ 𝑆: 𝐵 ∈ 𝐼 ⊆ 𝑆 ∪ 𝐵 𝐼 ⊆ 𝑆 𝐼𝑛𝑑𝑒𝑝. 𝐼 ⊆ 𝑆 ∪ 𝐵