《计算机科学》相关教学资源（参考文献）Approximate Counting via Correlation Decay in Spin Systems

Approximate Counting via correlation Decay inSpin Systems Yitong Yin Nanjing University Joint work with Liang Li (Peking U)and Pinyan Lu (MSRA)

Approximate Counting via Correlation Decay in Spin Systems Yitong Yin Nanjing University Joint work with Liang Li (Peking U) and Pinyan Lu (MSRA)

Two-State Spin System graph G=V,E)2 states {0,1 configuration V->10,1) contributions of local interactions: 0-0 weight: w(o)=contribution(e) e∈E

Two-State Spin System 2 states {0,1} configuration ￾ : V ￾ {0, 1} graph G=(V,E) contributions of local interactions: weight: w(￾) = ￾ e￾E KWV\ZQJ]\QWV(e) ￾ ￾ 1

Two-State Spin System graph G=(V,E)2 states {0,1} configuration o:V→{0，l} A= [=眼 contributions of local interactions: 020 weight: w(o）=A(),o(u） (u,v)∈E

Two-State Spin System A = ￾ A0,0 A0,1 A1,0 A1,1 ￾ = ￾ ￾ 1 1 ￾ ￾ 2 states {0,1} configuration ￾ : V ￾ {0, 1} graph G=(V,E) contributions of local interactions: weight: w(￾) = ￾ ￾ 1 ￾ (u,v)￾E A￾(u),￾(v)

Two-State Spin System graph G=(V,E)2 states {0,1) configuration o:V→{0，l} A- := weight:w()=]I A().() (u,v)∈E w(o) Gibbs measure: 4(o)= ZAG partition function: Z4(G)=〉(o) o∈{0,1}V

Two-State Spin System A = ￾ A0,0 A0,1 A1,0 A1,1 ￾ = ￾ ￾ 1 1 ￾ ￾ graph G=(V,E) 2 states {0,1} weight: w(￾) = ￾ (u,v)￾E A￾(u),￾(v) Gibbs measure: µ(￾) = w(￾) ZA(G) ZA(G) = ￾ ￾￾{0,1}V partition function: w(￾) configuration ￾ : V ￾ {0, 1}

Partition Function graph G=V,E)2 states (0,1 configuration o:V→{0，l} A= partition function: ZA(G)=∑ ΠA,a) o∈{0,1}V(u,w)∈E B=0,y=1 independent set vertex cover weighted Boolean CSP with one symmetric relation

Partition Function A = ￾ A0,0 A0,1 A1,0 A1,1 ￾ = ￾ ￾ 1 1 ￾ ￾ graph G=(V,E) 2 states {0,1} ZA(G) = ￾ ￾￾{0,1}V ￾ (u,v)￾E A￾(u),￾(v) partition function: ￾ = 0, ￾ = 1 # independent set # vertex cover configuration ￾ : V ￾ {0, 1} weighted Boolean CSP with one symmetric relation

Approximate Counting fix A= partition function: zA(G)=∑Π Aa(u),o(v) o∈{0,1}V(u,w)∈E is a well-define computational problem poly-time computable if By=1 or (B,Y)=(0,0) #P-hard if otherwise Approximation!

Approximate Counting ZA(G) = ￾ ￾￾{0,1}V ￾ (u,v)￾E A￾(u),￾(v) partition function: A = ￾ A0,0 A0,1 A1,0 A1,1 ￾ = ￾ ￾ 1 1 ￾ ￾ fix is a well-define computational problem poly-time computable if ￾￾ = 1 or (￾, ￾) = (0, 0) #P-hard if otherwise Approximation!

US93] Jerrum-Sinclair'93 [GJP03]Goldberg-Jerrum-Paterson'03 Y 3 ferromagnetic 2-state spin 2.5 87=1 FPRAS [GJP03] ferromagnetic Ising Model 1.5 anti- .FPRAS [JS93] ferromagnetic 1.11017 1 0≤B,Y≤1 0.5 no FPRAS unless NPCRP FPRAS [GJP03] [GJP03] 、heat-bath 8 0.5 1 1.5 2 2.5 3

0 0.5 1 1.5 2 2.5 3 0 0.5 1 1.5 2 2.5 3
0< , <1 = 1 uniqueness threshold threshold achieved by heatbath random walk 1.11017 0 ￾ ￾, ￾ ￾ 1 ￾ ￾ ferromagnetic Ising Model ferromagnetic 2-state spin FPRAS [JS93] FPRAS [GJP03] FPRAS [GJP03] heat-bath no FPRAS unless NP⊆RP [GJP03] anti￾ferromagnetic Goldberg-Jerrum-Paterson’03 Jerrum-Sinclair’93 [GJP03] [JS93]

Uniqueness Threshold 1.11017 1 0四 @(+ d 产0四 1.11017 元=f(金) 四 B Y f'()川<1 W 0 0 W 0 for all d B 0≤B<1<Y

    

    


 

         
            

       1.11017   Uniqueness Threshold f(x) = ￾￾x + 1 x + ￾ ￾d x ˆ = f(ˆx) |f￾ (ˆx)| < 1 0 ￾ ￾ < 1 < ￾ for all d

Our Result Y 3 2.5 ←—3y=1 2 1.5 ------- 1.11017 0≤B,Y≤1 0.5 FPTAS 8 0.5 1 1.5 2 2.5 3 B

0 0.5 1 1.5 2 2.5 3 0 0.5 1 1.5 2 2.5 3
0< , <1 = 1 uniqueness threshold threshold achieved by heatbath random walk 1.11017 0 ￾ ￾, ￾ ￾ 1 ￾ ￾ Our Result FPTAS

Marginal Distribution weight:w()=A(u).() (u,v)∈E w(o) Gibbs measure: L()=ZA(G) Z4(G)=∑ ΠA(w,o) o∈{0,1V(u,w)∈E marginal distributions at vertex v: p=Pr [o(v)=0] ΛCVoA∈{0,1}A fixed v∈A free vA Pr [o(v)=01(A)=OA]

Marginal Distribution weight: w(￾) = ￾ (u,v)￾E A￾(u),￾(v) Gibbs measure: µ(￾) = w(￾) ZA(G) ZA(G) = ￾ ￾￾{0,1}V ￾ (u,v)￾E A￾(u),￾(v) pv = 8Z ￾￾µ [￾(v) = 0] p￾￾ v = 8Z ￾￾µ [￾(v) = 0 | ￾(￾) = ￾￾] ￾￾ ￾ {0, 1}￾ marginal distributions at vertex v: ￾ ￾ V fixed v ￾ ￾ free v ￾￾ ￾