{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T17:14:15Z","timestamp":1744218855077},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T00:00:00Z","timestamp":1684281600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T00:00:00Z","timestamp":1684281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00037-023-00237-w","type":"journal-article","created":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T12:03:48Z","timestamp":1684325028000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory"],"prefix":"10.1007","volume":"32","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiguo","family":"Fu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Girstmair","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kowalczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,17]]},"reference":[{"key":"237_CR1","unstructured":"Miriam Backens (2017). A New Holant Dichotomy Inspired by Quantum\nComputation. In 44th International Colloquium on Automata, Languages, and Programming, volume 80, 16:1-16:14."},{"key":"237_CR2","unstructured":"Rodney J Baxter (1982). Exactly solved models in statistical mechanics.\nAcademic Press London."},{"key":"237_CR3","doi-asserted-by":"crossref","unstructured":"Andrei A Bulatov (2013). The complexity of the counting constraint\nsatisfaction problem. Journal of the ACM (JACM) 60(5), 1-41.","DOI":"10.1145\/2528400"},{"key":"237_CR4","doi-asserted-by":"crossref","unstructured":"Andrei A Bulatov, Martin Dyer, Leslie Ann Goldberg, Mark\nJerrum & Colin McQuillan (2013). The expressibility of functions on the boolean domain, with applications to counting CSPs. Journal of\nthe ACM (JACM) 60(5), 1-36.","DOI":"10.1145\/2528401"},{"key":"237_CR5","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai & Xi Chen (2017). Complexity of counting CSP with\ncomplex weights. Journal of the ACM (JACM) 64(3), 1-39.","DOI":"10.1145\/2822891"},{"key":"237_CR6","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai & Zhiguo Fu (2017). Holographic algorithm with matchgates\nis universal for planar# CSP over boolean domain. In the 49th ACM Symposium on Theory of Computing (STOC) SIAM Journal on\nComputing https:\/\/doi.org\/10.1137\/17M1131672 842-855.","DOI":"10.1137\/17M1131672"},{"key":"237_CR7","unstructured":"Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair & Michael Kowalczyk (2018). A Complexity Trichotomy for k-Regular Asymmetric\nSpin Systems Using Number Theory. In 9th Innovations in Theoretical\nComputer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, Anna R. Karlin, editor, volume 94 of LIPIcs, 2:1-2:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2018.2."},{"key":"237_CR8","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Zhiguo Fu, Heng Guo & Tyson Williams (2015). A\nHolant dichotomy: Is the FKT algorithm universal? In 2015 IEEE 56th\nAnnual Symposium on Foundations of Computer Science (FOCS). Theory Comput Syst (2021). https:\/\/doi.org\/10.1007\/s00224-021-10032-1, 1259-1276. IEEE.","DOI":"10.1007\/s00224-021-10032-1"},{"key":"237_CR9","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Zhiguo Fu, Heng Guo & Tyson Williams (2022).\nFKT is Not Universal - A Planar Holant Dichotomy for Symmetric Constraints. In Theory of Computing Systems volume 66(1), 143-308.","DOI":"10.1007\/s00224-021-10032-1"},{"key":"#cr-split#-237_CR10.1","unstructured":"Jin-Yi Cai, Zhiguo Fu & Shuai Shao (2021). New planar P-time"},{"key":"#cr-split#-237_CR10.2","doi-asserted-by":"crossref","unstructured":"computable six-vertex models and a complete complexity classification. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 1535-1547. SIAM.","DOI":"10.1137\/1.9781611976465.93"},{"key":"237_CR11","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai & Aaron Gorenstein (2014). Matchgates Revisited. Theory Comput. 10, 167-197.","DOI":"10.4086\/toc.2014.v010a007"},{"key":"237_CR12","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai & Michael Kowalczyk (2012). Spin systems on k-regular \ngraphs with complex edge functions. Theoretical Computer Science 461, 2-16.","DOI":"10.1016\/j.tcs.2012.01.021"},{"key":"237_CR13","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Michael Kowalczyk & Tyson Williams (2019). Gadgets\nand anti-gadgets leading to a complexity dichotomy. ACM Transactions on Computation Theory (TOCT) 11(2), 1-26.","DOI":"10.1145\/3305272"},{"key":"237_CR14","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2014). The complexity of\ncomplex weighted Boolean# CSP. Journal of Computer and System Sciences 80(1), 217-236.","DOI":"10.1016\/j.jcss.2013.07.003"},{"key":"237_CR15","unstructured":"S. Chowla (1964). A special infinite series. Kong. Norsk. Vidensk. Selsk. Forhandl 37, 85-87."},{"key":"237_CR16","doi-asserted-by":"crossref","unstructured":"S. Chowla (1970). The nonexistence of nontrivial linear relations\nbetween the roots of a certain irreducible equation. Journal of Number Theory 2(1), 120-123.","DOI":"10.1016\/0022-314X(70)90012-0"},{"key":"237_CR17","doi-asserted-by":"crossref","unstructured":"Martin Dyer, Leslie Ann Goldberg & Mark Jerrum (2009). The\ncomplexity of weighted Boolean# CSP. SIAM Journal on Computing 38(5), 1970-1986.","DOI":"10.1137\/070690201"},{"key":"237_CR18","doi-asserted-by":"crossref","unstructured":"Kurt Girstmair (1987). Character coordinates and annihilators of\ncyclotomic numbers. Manuscripta Mathematica 59(3), 375-389.","DOI":"10.1007\/BF01174800"},{"key":"237_CR19","doi-asserted-by":"crossref","unstructured":"Leslie Ann Goldberg & Mark Jerrum (2007). The complexity\nof ferromagnetic Ising with local fields. Combinatorics, Probability and Computing 16(1), 43-61.","DOI":"10.1017\/S096354830600767X"},{"key":"237_CR20","doi-asserted-by":"crossref","unstructured":"Heng Guo & Tyson Williams (2020). The complexity of planar\nBoolean# CSP with complex weights. Journal of Computer and System Sciences 107, 1-27.","DOI":"10.1016\/j.jcss.2019.07.005"},{"key":"237_CR21","doi-asserted-by":"crossref","unstructured":"Helmut Hasse (1971). On a question of S. Chowla. Acta Arithmetica\n18(1), 275-280.","DOI":"10.4064\/aa-18-1-275-280"},{"key":"237_CR22","doi-asserted-by":"crossref","unstructured":"Sangxia Huang & Pinyan Lu (2016). A dichotomy for real weighted\nHolant problems. Computational Complexity 25(1), 255-304.","DOI":"10.1007\/s00037-015-0118-3"},{"key":"237_CR23","doi-asserted-by":"crossref","unstructured":"Ernst Ising (1925). Beitrag zur theorie des ferromagnetismus.\nZeitschrift f\"ur Physik A Hadrons and Nuclei 31(1), 253-258.","DOI":"10.1007\/BF02980577"},{"key":"237_CR24","doi-asserted-by":"crossref","unstructured":"Mark Jerrum & Alistair Sinclair (1993). Polynomial-time approximation\nalgorithms for the Ising model. SIAM Journal on computing 22(5), 1087-1116.","DOI":"10.1137\/0222066"},{"key":"237_CR25","doi-asserted-by":"crossref","unstructured":"P. W. Kasteleyn (1961). The statistics of dimers on a lattice. Physica 27(12), 1209-1225.","DOI":"10.1016\/0031-8914(61)90063-5"},{"key":"237_CR26","unstructured":"P. W. Kasteleyn (1967). Graph theory and crystal physics. In Graph\ntheory and theoretical physics, (F. Harary, ed.) Academic Press, London 43-110."},{"key":"237_CR27","doi-asserted-by":"crossref","unstructured":"Richard E Ladner (1975). On the structure of polynomial time reducibility. Journal of the ACM (JACM) 22(1), 155-171.","DOI":"10.1145\/321864.321877"},{"key":"237_CR28","unstructured":"H. W. Lenstra & H Jager (1975). Linear independence of cosecant\nvalues. Nieuw Arch. Wisk 23(3), 131-144."},{"key":"237_CR29","doi-asserted-by":"crossref","unstructured":"Liang Li, Pinyan Lu & Yitong Yin (2013). Correlation decay up to\nuniqueness in spin systems. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, 67-84. SIAM.","DOI":"10.1137\/1.9781611973105.5"},{"key":"237_CR30","doi-asserted-by":"crossref","unstructured":"Jiabao Lin & Hanpin Wang (2018). The complexity of Boolean\nHolant problems with nonnegative weights. SIAM Journal on Computing 47(3), 798-828.","DOI":"10.1137\/17M113304X"},{"key":"237_CR31","doi-asserted-by":"crossref","unstructured":"Pinyan Lu & Yitong Yin (2016). Approximating the Partition Function\nof Two-Spin Systems. In Encyclopedia of Algorithms, 117-123.","DOI":"10.1007\/978-1-4939-2864-4_750"},{"key":"237_CR32","doi-asserted-by":"crossref","unstructured":"H. N. V. Temperley & M. E. Fisher (1961). Dimer problem in\nstatistical mechanics-an exact result. Philosophical Magazine 6(68), 1061-1063.","DOI":"10.1080\/14786436108243366"},{"key":"237_CR33","doi-asserted-by":"crossref","unstructured":"L. G. Valiant (2008). Holographic algorithms. SIAM Journal on Computing 37(5), 1565-1594.","DOI":"10.1137\/070682575"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00237-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00237-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00237-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T17:04:11Z","timestamp":1687885451000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00237-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,17]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["237"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00237-w","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,17]]},"assertion":[{"value":"23 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}