Introduction to the Correlation Decay Method Yitong Yin Nanjing University Introduction to Partition Functions Workshop,July 20,2018 Computational Aspects of Partition Functions,CIB@EPFL
Introduction to the Correlation Decay Method Yitong Yin Nanjing University Introduction to Partition Functions Workshop, July 20, 2018 Computational Aspects of Partition Functions, CIB@EPFL
July 20:Introduction to the correlation decay method (Yitong) July 23:Correlation decay for distributed counting (Yitong) July 25:Beyond bounded degree graphs (Piyush) July 26:Correlation decay,zeros of polynomials,and the Lovasz local lemma (Piyush)
• July 20: Introduction to the correlation decay method (Yitong) • July 23: Correlation decay for distributed counting (Yitong) • July 25: Beyond bounded degree graphs (Piyush) • July 26: Correlation decay, zeros of polynomials, and the Lovász local lemma (Piyush)
Counting Independent Set hardcore model:undirected graph G(V,E)fugacity>0 IV()T is an independent set in c otherwise partition function:Z=ZG(A)=>w(I) ICV e uniqueness threshold:Ac(A)= (△-1)A-1 (△-2)A △-2 Computing Zc()in graphs with constant max-degree <A ●入<λc(△)→FPTAS [Weitz06] strong spatial mixing ●λ>λc(△)→no FPRAS unless NP=RP [Galanis Stefankovie Vigoda 12][Sly Sun 12]
Counting Independent Set hardcore model: • λ < λc(Δ) 㱺 FPTAS • λ > λc(Δ) 㱺 no FPRAS unless NP=RP ∀ I ⊆ V: uniqueness threshold: Computing ZG(λ) in graphs with constant max-degree ≤ ∆ [Galanis Štefankovič Vigoda 12] [Sly Sun 12] [Weitz 06] undirected graph G(V,E) fugacity λ > 0 partition function: Z = ZG() = X I✓V w(I) w(I) = ( |I| I is an independent set in G 0 otherwise c() = ( 1)1 ( 2) ⟸ strong spatial mixing ⇡ e 2
Spin System undirected graph G=(V,E) finite integer g≥2 configuration o∈[gl' weight:w(o)=A(ou,)b(o) {u,w}∈E u∈V A:[ql×[q→R≥o symmetric gxg matrix (symmetric binary constraint) b:[q→R>0 g-vector (unary constraint) partition function: Zc=∑w(a) o∈[gV Gibbs distribution: c(o)= w(o) ZG
Spin System undirected graph G = (V, E) finite integer q ≥ 2 2 [q] V configuration w() = Y {u,v}2E A(u, v) Y v2V weight: b(v) A : [q] ⇥ [q] ! R0 b : [q] ! R0 symmetric q×q matrix q-vector (symmetric binary constraint) partition function: ZG = X 2[q]V w() Gibbs distribution: µG() = w() ZG (unary constraint)
undirected graph G=(V,E) finite integer q≥2 configuration o∈[glY weight:w()=A(ou,)b(o) {u,v}∈E v∈V ·2-spin system:q=2,o∈{0,1}V symmetric A= a00 a10 6= ●hardcore model: 4-81- ●Ising model ●multi-spin system:general g≥2 ●Potts model: 1 A= ●q-coloring:B:=0 1 b= 1.:1
• 2-spin system: q =2, • hardcore model: • Ising model: • multi-spin system: general q ≥ 2 • Potts model: • q-coloring: β=0 undirected graph G = (V, E) 2 [q] V configuration w() = Y {u,v}2E A(u, v) Y v2V weight: b(v) 2 {0, 1}V 1 1 2 6 6 6 4 ... 3 7 7 7 A = 5 2 6 4 1 . . . 1 3 7 b = 5 A = a00 a01 a10 a11 b = b0 b1 A = 0 1 1 1 b = 1 A = 1 1 symmetric finite integer q ≥ 2 b = 1