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