Spin System Aa Ab Ae:[g]×[g→R≥o Af Fv:[gl→R≥0 F Ae F partition function:count the of solutions to an CSP Ⅱe(ru,)Π，(c》 ∈[qy e=uw∈E w∈V enumerate all binary constraints unary constraints configurations 17 1 coloring:A= F .. 1
Spin System Z = X x2[q]V Y e=uv2E Ae(xu, xv) Y v2V Fv(xv) Aa Ab Ac Ad Ae Af Fw Fu Fv Fy Fx enumerate all configurations binary constraints unary constraints A = 2 6 6 6 4 0 0 ... 0 3 7 7 7 5 1 1 F = 2 6 6 6 4 1 1 . . . 1 3 7 7 7 5 Ae : [q] ⇥ [q] ! R0 Fv : [q] ! R0 coloring: partition function: count the # of solutions to an CSP
Examples of Spin systems ●2-spin:q=2 hardcore model (independent set),Ising model,etc. multi-spin:general q ·coloring: 111
• 2-spin: q=2 • hardcore model (independent set), Ising model, etc. • multi-spin: general q • coloring: Examples of Spin systems A = 2 6 6 6 4 0 0 ... 0 3 7 7 7 5 1 1 F = 2 6 6 6 4 1 1 . . . 1 3 7 7 7 5
Examples of Spin systems 。2-spin:q=2 hardcore model (independent set),Ising model,etc. multi-spin:general q ●coloring: A= Potts model:inverse temperature B A- arbitrary F when B=-0o and F=(1,1,..,1),it is coloring
• 2-spin: q=2 • hardcore model (independent set), Ising model, etc. • multi-spin: general q • coloring: • Potts model: inverse temperature β Examples of Spin systems 1 1 A = 2 6 6 6 4 e e ... e 3 7 7 7 5 arbitrary F when β=-∞ and F=(1,1,... ,1), it is coloring A = 2 6 6 6 4 0 0 ... 0 3 7 7 7 5 1 1 F = 2 6 6 6 4 1 1 . . . 1 3 7 7 7 5
Results sufficient conditions for FPTAS for classes of spin systems coloring:q≥ox△+β randomized algorithms:by simulating a random walk (the Glauber dynamics)over colorings a=11/6 (Jerrum'95Bubley-Dyer'97+Vigoda'99) deterministic algorithms:by exploiting the correlation decay (spatial mixing)property .8432 (Gamarnik-Katz'07) just correlation decay(no FPTAS):a~1.763 (Goldberg-Martin-Paterson'05,Gamarnik-Katz-Misra'12) this paper:deterministic FPTAS for a2.58071
Results • coloring: q ≥αΔ+β • randomized algorithms: by simulating a random walk (the Glauber dynamics) over colorings • α=11/6 (Jerrum’95⇢Bubley-Dyer’97⇢Vigoda’99) • deterministic algorithms: by exploiting the correlation decay (spatial mixing) property • α≈2.8432 (Gamarnik-Katz’07) • just correlation decay (no FPTAS): α≈1.763 (Goldberg-Martin-Paterson’05, Gamarnik-Katz-Misra’12) sufficient conditions for FPTAS for classes of spin systems this paper: deterministic FPTAS for α≈2.58071
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,2) w,x,y,z∈[q ●( Gamarnik-Katz'07:(cA-c-a)△g△<1 this paper::3△(cA-1)≤1 an exponential improvement! on Potts model (with inverse temperature B): it implies:3△(ell-1)≤1
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 an exponential improvement!