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