{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:45Z","timestamp":1759638585485,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T00:00:00Z","timestamp":1550361600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0914969 and CCF-1714275"],"award-info":[{"award-number":["CCF-0914969 and CCF-1714275"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            We introduce an idea called\n            <jats:italic>anti-gadgets<\/jats:italic>\n            for reductions in complexity theory. These anti-gadgets are presented as graph fragments, but their effect is equivalent to erasing the presence of other graph fragments, as if we had managed to include a negative copy of a certain graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function\n            <jats:italic>Z<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) of spin systems over 3-regular directed graphs\n            <jats:italic>G<\/jats:italic>\n            ,\n            <jats:italic>Z<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) = \u2211\n            <jats:sub>\n              \u03c3 :\n              <jats:italic>V<\/jats:italic>\n              (\n              <jats:italic>G<\/jats:italic>\n              ) \u2192 { 0,1}\n            <\/jats:sub>\n            \u220f\n            <jats:sub>\n              (\n              <jats:italic>u<\/jats:italic>\n              ,\n              <jats:italic>v<\/jats:italic>\n              ) \u2208\n              <jats:italic>E<\/jats:italic>\n              (\n              <jats:italic>G<\/jats:italic>\n              )\n            <\/jats:sub>\n            <jats:italic>f<\/jats:italic>\n            (\u03c3 (\n            <jats:italic>u<\/jats:italic>\n            ), \u03c3 (\n            <jats:italic>v<\/jats:italic>\n            )), where each edge is given a (not necessarily symmetric) complex-valued binary function\n            <jats:italic>f<\/jats:italic>\n            : { 0,1}\n            <jats:sup>2<\/jats:sup>\n            \u2192 C. We show that\n            <jats:italic>Z<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) is either computable in polynomial time or #P-hard, depending explicitly on\n            <jats:italic>f<\/jats:italic>\n            . When the input graph\n            <jats:italic>G<\/jats:italic>\n            is planar, there is an additional class of polynomial time computable partition functions\n            <jats:italic>Z<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ), while everything else remains #P-hard. Furthermore, this additional class is precisely those that can be transformed by a holographic reduction to matchgates, followed by the Fisher-Kasteleyn-Temperley algorithm via Pfaffians.\n          <\/jats:p>","DOI":"10.1145\/3305272","type":"journal-article","created":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T20:54:15Z","timestamp":1550609655000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy"],"prefix":"10.1145","volume":"11","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[{"name":"University of Wisconsin\u2013Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kowalczyk","sequence":"additional","affiliation":[{"name":"Northern Michigan University, Marquette, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tyson","family":"Williams","sequence":"additional","affiliation":[{"name":"Blocher Consulting, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,17]]},"reference":[{"volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","year":"2017","author":"Backens Miriam","key":"e_1_2_2_1_1"},{"key":"e_1_2_2_2_1","unstructured":"Miriam Backens. 2017. A new Holant dichotomy inspired by quantum computation. CoRR abs\/1702.00767 (2017).  Miriam Backens. 2017. A new Holant dichotomy inspired by quantum computation. CoRR abs\/1702.00767 (2017)."},{"key":"e_1_2_2_3_1","unstructured":"Rodney J. Baxter. 1982. Exactly Solved Models in Statistical Mechanics. Academic Press London.  Rodney J. Baxter. 1982. Exactly Solved Models in Statistical Mechanics. Academic Press London."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175423"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.49"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032314"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9092-8"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1049798"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9626-6"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.01.021"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.12.043"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090272"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.005"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536511"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/100814585"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.039"},{"volume-title":"SODA\u201911","author":"Cai Jin-Yi","key":"e_1_2_2_20_1"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0044-6"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.07.003"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1073984"},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Nadia Creignou Sanjeev Khanna and Madhu Sudan. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems. Society for Industrial and Applied Mathematics.   Nadia Creignou Sanjeev Khanna and Madhu Sudan. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems. Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898718546"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/070690201"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314691"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/360708.360731"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806789"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811258"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"e_1_2_2_31_1","unstructured":"Heng Guo Sangxia Huang Pinyan Lu and Mingji Xia. 2011. The complexity of weighted Boolean #CSP modulo k. In STACS\u201911. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik 249--260.  Heng Guo Sangxia Huang Pinyan Lu and Mingji Xia. 2011. The complexity of weighted Boolean #CSP modulo k . In STACS\u201911. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik 249--260."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/100815530"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"volume-title":"Retrieved","year":"2010","author":"Kowalczyk Michael","key":"e_1_2_2_34_1"},{"key":"e_1_2_2_35_1","unstructured":"Michael Kowalczyk and Jin-Yi Cai. 2010. Holant problems for regular graphs with complex edge functions. In STACS. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 525--536.  Michael Kowalczyk and Jin-Yi Cai. 2010. Holant problems for regular graphs with complex edge functions. In STACS. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 525--536."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9671-7"},{"key":"e_1_2_2_37_1","first-page":"3","article-title":"Operations with structures","volume":"18","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1967","journal-title":"Acta Math. Hung."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786436108243366"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797321602"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.023"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3305272","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3305272","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3305272","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:58:09Z","timestamp":1750208289000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3305272"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,17]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3305272"],"URL":"https:\/\/doi.org\/10.1145\/3305272","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,2,17]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}