《计算机科学》相关教学资源（参考文献）Approximate Counting via Correlation Decay on Planar Graphs

Approximate Counting via correlation Decay on Planar Graphs Yitong Yin Nanjing University Chihao Zhang Shanghai Jiaotong University

Approximate Counting via Correlation Decay on Planar Graphs Yitong Yin Nanjing University Chihao Zhang Shanghai Jiaotong University

Holant Problems (Valiant 2004) instance: =(G(V,E),fuvEv) graph G=(V,目 edges:variables (domain [q]) vertices:constraints(arity=degree) symmetric f:[g]deg()C configuration (solution,coloring,..):[ holant(counting): holant(2)=>II fu (lE()) o∈[g]Ev∈V #matchings: q-2 E{0,1f=AT-MOST-ONE

Holant Problems edges: variables (domain [q]) vertices: constraints (arity=degree) graph G=(V,E) holant (counting): PWTIV\(￾) = ￾ ￾￾[q]E ￾ v￾V fv ￾ ￾ |E(v) ￾ ￾ = (G(V,E), {fv}v￾V ) fv (Valiant 2004) configuration (solution, coloring, ...): instance: fv : [q] LMO(v) ￾ C #matchings: q=2 ￾ ￾ {0, 1} fv ￾At-Most-One E ￾ ￾ [q] E symmetric

Holant problem:Holant(9,F) graph family function family mptR-G,e）wm{食 output:holant()=>f(()) o∈[g]Ev∈V spin system /graph homomorphism(G.H.): F={f:[ga→C,d≤2}U{=} ●S,#VC .#q-colorings,#H-colorings .hardcore/lsing/Potts models,MRF G=(V,目 spin model holant

Holant problem: PWTIV\(￾) = ￾ ￾￾[q]E ￾ v￾V fv ￾ ￾ |E(v) ￾ ￾ = (G(V,E), {fv}v￾V ) 0WTIV\(G, F) graph family function family input: output: ￾ G ￾ G fv ￾ F with F = {f : [q] d ￾ C, d ￾ 2} ￾ {=} spin system / graph homomorphism (G.H.): • #IS, #VC • #q-colorings, #H-colorings • hardcore/Ising/Potts models, MRF f G=(V,E) V E = = = = f f f f f spin model holant

Holant Problems Holant problem:Holant(G,F) graph family function family characterize the tractability of Holant(g,F)by g and F Bad news:for general/planar G,almost all nontrivial F:#P-hard (Dyer-Greenhill'00,Bulatov-Grohe'05,Dyer-Goldberg'07,Bulatov'08,Goldberg-Grohe-Jerrum'10,Cai-Chen'10, Cai-Chen-Lu'10,Cai-Lu-Xia'10,Dyer-Richerby'10,Dyer-Richerby'11,Cai-Chen'12,Cai-Lu-Xia'13) Good news:tractable if g is tree,F is Spin or Matching (arity≤2'and=）(At-Most-One) Our result: g is planar (locally like a tree) F is regular li/nEPFAS) correlation decay local info is enough)

Holant Problems Holant problem: 0WTIV\(G, F) graph family function family Bad news: for general/planar , almost all nontrivial : #P-hard (Dyer-Greenhill’00, Bulatov-Grohe’05, Dyer-Goldberg’07, Bulatov’08, Goldberg-Grohe-Jerrum’10, Cai-Chen’10, Cai-Chen-Lu’10, Cai-Lu-Xia’10, Dyer-Richerby’10, Dyer-Richerby’11, Cai-Chen’12, Cai-Lu-Xia’13) G F Good news: tractable if is G tree, is F Spin or Matching (arity≤2 and =) (At-Most-One) Our result: correlation decay G is planar F is regular (local info is enough) (locally like a tree) (like spin/matching) ￾ FPTAS characterize the tractability of by and 0WTIV\(G, F) G F

Gibbs measure =(G(V;E),{fu}vEv) f:[g]ego）→R≥o holant(()=Πf,(oE() o∈[glEv∈V Gibbs measure:Pr()= Πevf(oE(w) holant marginal probability:E[a)4 ACE Pr(a(e)=cA) self compute reduction FPTAS for Pr(o(e)=c|TA)±是 holant(S) in time poly(n)

Gibbs Measure PWTIV\(￾) = ￾ ￾￾[q]E ￾ v￾V fv ￾ ￾ |E(v) ￾ ￾ = (G(V,E), {fv}v￾V ) Gibbs measure: marginal probability: fv : [q] LMO(v) ￾ R￾0 8Z(￾) = ￾ v￾V fv(￾|E(v)) PWTIV\ A ￾ E FPTAS for PWTIV\(￾) self￾reduction 8Z(￾(e) = c | ￾A) ￾A ￾ [q] A compute in time 8Z(￾(e) = c | ￾A) ± 1 n XWTa (n)

Correlation Decay strong spatial mixing(SSM):VoB E[a]5 Pr(a(e)=cA)-Pr(o(e)=cA,OB) ≤poly(IVI)exp(-2(t) SSM:sufficiency of local information for approx.of Pr((e)=cA) efficiency of local computation (FPTAS) such implication was known for: g-2,F is Spin (Weitz6) Matching (Bayati-Gamarnik-Katz-Nair-Tetali'08)

Correlation Decay strong spatial mixing (SSM): SSM: sufficiency of local information B G e t A ￾ XWTa(|V |) M`X(￾￾(t)) ￾￾B ￾ [q] B ? for approx. of efficiency of local computation 8Z(￾(e) = c | ￾A) q=2, is F Spin (Weitz’06) Matching (Bayati-Gamarnik-Katz-Nair-Tetali’08) ￾ such implication was known for: (FPTAS) ￾ ￾8Z(￾(e) = c | ￾A) ￾ 8Z(￾(e) = c | ￾A, ￾B) ￾ ￾

Regularity Pinning: symmetric f:[gla→cT∈gk Pin(f)=g where g:[g]d-kC Vo E [q]d-k,g(o)=f(o1,...;od-k;TI,...,Tk) when q-2 write f=[fo,f1,...,fa] where f;=f(a)thatol1 =i a family F of symmetric functions is regular if ヨa finite C s.t.Vf∈F,fisC-regular fo.a-1 fal examples:bounded-arity d-k+1 equality [1,0,...01] counterexample:0.1.0..... at-most-one [1,1,0,...,0] cyclic [a,b.c,a,b.c,.]

￾ ￾￾ ￾ d￾k+1 Regularity 8QV￾ (f) = g g : [q] d￾k ￾ C f : [q] symmetric d ￾ C where ￾￾ ￾ [q] g(￾) = f(￾1,..., ￾d￾k, ￾1,..., ￾k) d￾k , ￾ ￾ [q] k Pinning: f : [q] is C-regular if symmetric d ￾ C ￾ ￾ ￾ 8QV￾ (f) | ￾￾ ￾ [q] k￾￾ ￾0 ￾ k ￾ d, ￾ ￾ C a family of symmetric functions is F regular if ￾ a finite C s.t. ￾f ￾ F, f is C-regular counterexample: [0,..., 0 ￾ ￾￾ ￾ d 2 , 1, 0,..., 0 ￾ ￾￾ ￾ d 2 ] [f0, f1, f2,...,fi,...,fd￾1, fd] examples: equality [1,0,...,0,1] at-most-one [1,1,0,...,0] cyclic [a,b,c,a,b,c,...] bounded-arity when q=2 write f = [f0, f1,...,fd] where fi = f(￾) that ￾￾￾1 = i

Holant can be computed F is Spin (junction-tree BP) in time poly(n)ifhas bounded-arity (tensor network,Markov-Shi'09) Theorem I If F is regular,then holant(G,{fvvF) can be computed in time poly(.(treewidth(G)) Theorem II If g is planar (apex-minor-free),F is regular,then SSM FPTAS for Holant(g,F)

0WTIV\(G, F) Theorem II If G is planar (apex-minor-free), F is regular, then SSM FPTAS for XWTa(n) · 2 if \_ in time F is Spin (junction-tree BP) has bounded-arity (tensor network, Markov-Shi’09) ￾ F Holant can be computed If F is regular, then PWTIV\(G, {fv}v￾V ￾ F) can be computed in time Theorem I XWTa(|V |) · 2O(\ZMM_QL\P(G))

Theorem I If F is regular,then holant(G,{fvvF) can be computed in time poly(.2(treewidth(G)) SSM: Pr(a(e)=clA)-Pr(o(e)=clA,OB)<poly(V)exp(-t) compute Pr(g(e)=c|TA)±是 FPTAS in time poly(n) for Holant Theorem(Demaine-Hajiaghayi'04) For apex-minor-free graphs, treewidth of t-ball is O(). Theorem II If g is planar (apex-minor-free),F is regular,then SSM FPTAS for Holant(g,F)

0WTIV\(G, F) Theorem II If G is planar (apex-minor-free), F is regular, then SSM FPTAS for SSM: G B e t A ￾ ￾8Z(￾(e) = c | ￾A) ￾ 8Z(￾(e) = c | ￾A, ￾B) ￾ ￾ ￾ XWTa(|V |) M`X(￾t) Theorem (Demaine-Hajiaghayi’04) For apex-minor-free graphs, treewidth of t-ball is O(t). compute in time 8Z(￾(e) = c | ￾A) ± 1 n XWTa (n) FPTAS for Holant If F is regular, then PWTIV\(G, {fv}v￾V ￾ F) can be computed in time Theorem I XWTa(|V |) · 2O(\ZMM_QL\P(G))

Theorem I If F is regular,then holant(G,{fvvF) can be computed in time poly().2(treewidth(G)) tree-decomposition: B a tree of"bags"of vertices: I.Every vertex is in some bag. E 2.Every edge is in some bag. 3.If two bags have a same vertex, A B B then all bags in the path between them have that vertex. width:max bag size-1 treewidth:width of optimal H tree decomposition

tree-decomposition: 1.Every vertex is in some bag. 2.Every edge is in some bag. 3.If two bags have a same vertex, then all bags in the path between them have that vertex. a tree of “bags” of vertices: width: max bag size -1 treewidth: width of optimal tree decomposition If F is regular, then PWTIV\(G, {fv}v￾V ￾ F) can be computed in time Theorem I XWTa(|V |) · 2O(\ZMM_QL\P(G))