Improved FPTAS for Multi-spin Systems Pinyan Lu Yitong Yin Microsoft Research Asia Nanjing University presented by: Sangxia Huang KTH
Improved FPTAS for Multi-spin Systems presented by: Sangxia Huang KTH Yitong Yin Nanjing University Pinyan Lu Microsoft Research Asia
Colorings instance:undirected G(V,E)with max-degree <A g colors: g a goal:counting the number of proper g-colorings for G exact counting is #P-hard 。when g<△，decision of existence is NP-hard
Colorings instance: undirected G(V,E) with max-degree ≤Δ goal: counting the number of proper q-colorings for G q colors: • exact counting is #P-hard • when q<Δ , decision of existence is NP-hard
Colorings instance:undirected G(V,E)with max-degree <A q colors: goal:counting the number of proper g-colorings for G exact counting is #P-hard ·when g<△，decision of existence is NP-hard approximately counting the number of proper q-colorings for G when g≥△+β equivalent to sampling an almost uniform random q-coloring
Colorings instance: undirected G(V,E) with max-degree ≤Δ goal: counting the number of proper q-colorings for G q colors: • exact counting is #P-hard • when q<Δ , decision of existence is NP-hard approximately counting the number of proper q-colorings for G when q ≥αΔ+β equivalent to sampling an almost uniform random q-coloring
Spin System (pairwise Markov random field) instance: ·undirected G(V,E); Ad ·q states:[q]; each edge eEE associated with an activity: a symmetric nonnegative gxg matrix Ae:[gl×[gl→R≥o each vertex veV associated with an external field: a nonnegative q-vector F:gR> goal:computing the partition function: Z=ΠAe(cu,x）ΠF(c) c∈[glVe=uw∈E v∈V
Spin System (pairwise Markov random field) • undirected G(V,E); • q states: [q]; • each edge e∈E associated with an activity: • each vertex v∈V associated with an external field: Ae : [q] ⇥ [q] ! R0 a symmetric nonnegative q×q matrix a nonnegative q-vector Fv : [q] ! R0 instance: Z = X x2[q]V Y e=uv2E Ae(xu, xv) Y v2V Fv(xv) goal: computing the partition function: Aa Ab Ac Ad Ae Af Fw Fu Fv Fy Fx
Spin System Aa Ab Ae:[g]×[ql→R≥0 A Fv:[gl→R≥0 EAe户 partition function:count the of solutions to an CSP z-∑) Πe(cw,x)ΠE(x) ∈9y e=uw∈E 入 v∈V enumerate all binary constraints unary constraints configurations
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 Ae : [q] ⇥ [q] ! R0 Fv : [q] ! R0 partition function: count the # of solutions to an CSP
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!