Results sufficient conditions for FPTAS for classes of spin systems general multi-spin system: Ae(x,y) in terms of c= max e∈D Ae（w,z) w,x,y,z∈[q ● Gamarnik-Katz'07:(cA-c△)△g<1 this paper::3△(cA-1)≤1 an exponential improvement! ●on Potts model(with inverse temperatureβ)： it implies::3△(ell-1)≤1 confirming the conjecture of B=()in [GK'07] asymptotically matching thee<1-inaproximability bound for B<0 in [Galanis-Stefankovic-Vigoda'13]
Results • general multi-spin system: • Gamarnik-Katz’07: • on Potts model (with inverse temperature β): sufficient conditions for FPTAS for classes of spin systems (c c)q < 1 in terms of it implies: 3(e|| 1) 1 c = max e2E w,x,y,z2[q] Ae(x, y) Ae(w, z) this paper: 3(c 1) 1 • confirming the conjecture of in [GK’07] • asymptotically matching the inaproximability bound for in [Galanis-Stefankovic-Vigoda’13] e < 1 q < 0 || = O 1 an exponential improvement!
The standard first step: reducing to the computing of marginal probability Z=∑ΠAe(u,)IF(x) c∈[glVe=uv∈E U∈V for any configuration E [a] Gibbs measure: P[X==Ⅱe=EB Ae(ru,)leyP(e） Z marginal probability:P[X.=]
The standard first step: reducing to the computing of marginal probability Z = X x2[q]V Y e=uv2E Ae(xu, xv) Y v2V Fv(xv) for any configuration x 2 [q] V Gibbs measure: marginal probability: P[X = x] = Q e=uv2E Ae(xu, xv) Q v2V Fv(xv) Z P[Xv = xv]
The standard first step: reducing to the computing of marginal probability Z=∑ΠAe(xu,x)ΠF(c) c∈[g]Ve=uweE u∈V for any configuration e[a] Gibbs measure: P[X=x]= le=UvEB Ae(cu,cu)ΠeyF,(cu） Z marginal probability:P[X.=] Jerrum-Valiant-Vazirani'86 for self-reducible class of spin-systems: efficient approximation of marginal probability FPTAS for Z (with additive error)
The standard first step: reducing to the computing of marginal probability Z = X x2[q]V Y e=uv2E Ae(xu, xv) Y v2V Fv(xv) for any configuration x 2 [q] V Gibbs measure: marginal probability: P[X = x] = Q e=uv2E Ae(xu, xv) Q v2V Fv(xv) Z P[Xv = xv] for self-reducible class of spin-systems: efficient approximation of marginal probability (with additive error) FPTAS for Z Jerrum-Valiant-Vazirani’86