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() = eE 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] antiferromagnetic 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