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