{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:33Z","timestamp":1781077833373,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T00:00:00Z","timestamp":1609372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61902241, 61922052 and 61932002"],"award-info":[{"award-number":["61902241, 61922052 and 61932002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Science and Technology Innovation 2030\u2014\u201cNew Generation of Artificial Intelligence\u201d","award":["2018AAA0100903"],"award-info":[{"award-number":["2018AAA0100903"]}]},{"name":"Innovation Program of Shanghai Municipal Education Commission"},{"name":"Innovative Research Team of Shanghai University of Finance and Economics"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,1,31]]},"abstract":"<jats:p>We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second-order recurrence modulo in a couple of exceptional cases. As a consequence, any non-negative Holant problem on cubic graphs has an efficient approximation algorithm unless the problem is equivalent to approximately counting perfect matchings, a central open problem in the area. This is in sharp contrast to the computational phase transition shown by two-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting.<\/jats:p>","DOI":"10.1145\/3418056","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T18:48:01Z","timestamp":1609440481000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Zeros of Holant Problems"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8199-5596","authenticated-orcid":false,"given":"Heng","family":"Guo","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chao","family":"Liao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chihao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1143\/JPSJ.29.350"},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"A complete dichotomy for complex-valued Holantc","volume":"107","author":"Backens Miriam","year":"2018","journal-title":"Proceedings of the ICALP (LIPIcs)"},{"key":"e_1_2_1_3_1","volume-title":"Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics","author":"Barvinok Alexander I."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250809"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_2_1_6_1","volume-title":"Complexity Dichotomies for Counting Problems","author":"Cai Jin-Yi"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2822891"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1049798"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/100814585"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the SODA. 1802--1821","author":"Cai Jin-Yi","year":"2018"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(03)00078-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2011.10.030"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2822322"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811258"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-06-00529-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000401"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10090"},{"key":"e_1_2_1_19_1","first-page":"352","article-title":"The zeros of a polynomial","volume":"11","author":"Grace John H.","year":"1902","journal-title":"Proc. Camb. Philos. Soc."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch38"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627822"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.25"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M113304X"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.95"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_65"},{"key":"e_1_2_1_30_1","volume-title":"Approximating Holant problems by winding. CoRR abs\/1301.2880","author":"McQuillan Colin","year":"2013"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101003"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1541667626"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3506-7"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.26.303"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/312570.312587"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002200050522"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.indag.2013.04.004"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-014-0947-5"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the LATIN. 873--885","author":"\u0160tefankovi\u010d Daniel","year":"2018"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01485280"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1922-1501220-0"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418056","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:35Z","timestamp":1750195895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418056"}},"subtitle":["Locations and Algorithms"],"short-title":[],"issued":{"date-parts":[[2020,12,31]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3418056"],"URL":"https:\/\/doi.org\/10.1145\/3418056","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,31]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}