{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T15:45:59Z","timestamp":1743090359256,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031496134"},{"type":"electronic","value":"9783031496141"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"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":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-49614-1_5","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T14:02:45Z","timestamp":1702044165000},"page":"83-96","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Restricted Holant Dichotomy on\u00a0Domains 3 and\u00a04"],"prefix":"10.1007","author":[{"given":"Yin","family":"Liu","sequence":"first","affiliation":[]},{"given":"Austen Z.","family":"Fan","sequence":"additional","affiliation":[]},{"given":"Jin-Yi","family":"Cai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"issue":"6","key":"5_CR1","doi-asserted-by":"publisher","first-page":"1739","DOI":"10.1137\/20M1311557","volume":"50","author":"M Backens","year":"2021","unstructured":"Backens, M.: A full dichotomy for $$\\operatorname{Holant}^{c}$$, inspired by quantum computation. SIAM J. Comput. 50(6), 1739\u20131799 (2021). https:\/\/doi.org\/10.1137\/20M1311557","journal-title":"SIAM J. Comput."},{"issue":"2","key":"5_CR2","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/3381425","volume":"16","author":"M Backens","year":"2020","unstructured":"Backens, M., Goldberg, L.A.: Holant clones and the approximability of conservative Holant problems. ACM Trans. Algorithms 16(2), 23:1-23:55 (2020). https:\/\/doi.org\/10.1145\/3381425","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"AA Bulatov","year":"2006","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. JACM 53(1), 66\u2013120 (2006). https:\/\/doi.org\/10.1145\/1120582.1120584","journal-title":"JACM"},{"issue":"3","key":"5_CR4","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/2822891","volume":"64","author":"JY Cai","year":"2017","unstructured":"Cai, J.Y., Chen, X.: Complexity of counting CSP with complex weights. JACM 64(3), 19:1-19:39 (2017). https:\/\/doi.org\/10.1145\/2822891","journal-title":"JACM"},{"issue":"6","key":"5_CR5","doi-asserted-by":"publisher","first-page":"2177","DOI":"10.1137\/15M1032314","volume":"45","author":"JY Cai","year":"2016","unstructured":"Cai, J.Y., Chen, X., Lu, P.: Nonnegative weighted# CSP: an effective complexity dichotomy. SIAM J. Comput. 45(6), 2177\u20132198 (2016). https:\/\/doi.org\/10.1137\/15M1032314","journal-title":"SIAM J. Comput."},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Cai, J., Guo, H., Williams, T.: The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18\u201321, 2014, pp. 601\u2013610. IEEE Computer Society (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.70","DOI":"10.1109\/FOCS.2014.70"},{"issue":"5","key":"5_CR7","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/15M1049798","volume":"45","author":"JY Cai","year":"2016","unstructured":"Cai, J.Y., Guo, H., Williams, T.: A complete dichotomy rises from the capture of vanishing signatures. SIAM J. Comput. 45(5), 1671\u20131728 (2016). https:\/\/doi.org\/10.1137\/15M1049798","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jcss.2010.06.005","volume":"77","author":"JY Cai","year":"2011","unstructured":"Cai, J.Y., Lu, P.: Holographic algorithms: from art to science. J. Comput. Syst. Sci. 77(1), 41\u201361 (2011). https:\/\/doi.org\/10.1016\/j.jcss.2010.06.005","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR9","doi-asserted-by":"publisher","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates and Holographic reductions for hardness. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 644\u2013653 (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.34","DOI":"10.1109\/FOCS.2008.34"},{"key":"5_CR10","doi-asserted-by":"publisher","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holant problems and counting CSP. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 715\u2013724 (2009). https:\/\/doi.org\/10.1145\/1536414.1536511","DOI":"10.1145\/1536414.1536511"},{"key":"5_CR11","doi-asserted-by":"publisher","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Dichotomy for Holant* problems with domain size 3. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, pp. 1278\u20131295. SIAM (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.93","DOI":"10.1137\/1.9781611973105.93"},{"issue":"3","key":"5_CR12","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1137\/16M1073984","volume":"46","author":"JY Cai","year":"2017","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holographic algorithms with matchgates capture precisely tractable planar #CSP. SIAM J. Comput. 46(3), 853\u2013889 (2017). https:\/\/doi.org\/10.1137\/16M1073984","journal-title":"SIAM J. Comput."},{"issue":"3","key":"5_CR13","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/100811258","volume":"42","author":"M Dyer","year":"2013","unstructured":"Dyer, M., Richerby, D.: An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput. 42(3), 1245\u20131274 (2013). https:\/\/doi.org\/10.1137\/100811258","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1090\/S0894-0347-06-00529-7","volume":"20","author":"M Freedman","year":"2007","unstructured":"Freedman, M., Lov\u00e1sz, L., Schrijver, A.: Reflection positivity, rank connectivity, and homomorphism of graphs. J. Amer. Math. Soc. 20(1), 37\u201351 (2007)","journal-title":"J. Amer. Math. Soc."},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2018.09.012","volume":"264","author":"Z Fu","year":"2019","unstructured":"Fu, Z., Yang, F., Yin, M.: On blockwise symmetric matchgate signatures and higher domain #CSP. Inf. Comput. 264, 1\u201311 (2019). https:\/\/doi.org\/10.1016\/j.ic.2018.09.012","journal-title":"Inf. Comput."},{"key":"5_CR16","doi-asserted-by":"publisher","unstructured":"Guo, H., Huang, S., Lu, P., Xia, M.: The complexity of weighted Boolean #CSP modulo $$k$$. In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS, pp. 249\u2013260 (2011). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2011.249","DOI":"10.4230\/LIPIcs.STACS.2011.249"},{"issue":"1","key":"5_CR17","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1137\/100815530","volume":"42","author":"H Guo","year":"2013","unstructured":"Guo, H., Lu, P., Valiant, L.G.: The complexity of symmetric Boolean parity Holant problems. SIAM J. Comput. 42(1), 324\u2013356 (2013). https:\/\/doi.org\/10.1137\/100815530","journal-title":"SIAM J. Comput."},{"key":"5_CR18","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28. Oxford University Press (2004)"},{"issue":"1","key":"5_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00224-016-9671-7","volume":"59","author":"M Kowalczyk","year":"2016","unstructured":"Kowalczyk, M., Cai, J.Y.: Holant problems for 3-regular graphs with complex edge functions. Theory Comput. Syst. 59(1), 133\u2013158 (2016). https:\/\/doi.org\/10.1007\/s00224-016-9671-7","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"5_CR20","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1090\/S0894-0347-07-00568-1","volume":"20","author":"B Szegedy","year":"2007","unstructured":"Szegedy, B.: Edge coloring models and reflection positivity. J. Am. Math. Soc. 20(4), 969\u2013988 (2007)","journal-title":"J. Am. Math. Soc."},{"key":"5_CR21","first-page":"327","volume-title":"Edge Coloring Models as Singular Vertex Coloring Models","author":"B Szegedy","year":"2010","unstructured":"Szegedy, B.: Edge Coloring Models as Singular Vertex Coloring Models, pp. 327\u2013336. Bolyai Society Mathematical Studies. Springer, Berlin Heidelberg pp (2010)"},{"key":"5_CR22","doi-asserted-by":"publisher","unstructured":"Valiant, L.G.: Accidental algorithms. In: 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 509\u2013517. IEEE (2006). https:\/\/doi.org\/10.1109\/FOCS.2006.7","DOI":"10.1109\/FOCS.2006.7"},{"issue":"5","key":"5_CR23","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"LG Valiant","year":"2008","unstructured":"Valiant, L.G.: Holographic algorithms. SIAM J. Comput. 37(5), 1565\u20131594 (2008). https:\/\/doi.org\/10.1137\/070682575","journal-title":"SIAM J. Comput."},{"key":"5_CR24","unstructured":"Xia, M.: Holographic reduction: a domain changed application and its partial converse theorems. Int. J. Softw. Informatics 5(4), 567\u2013577 (2011). https:\/\/www.ijsi.org\/ch\/reader\/view_abstract.aspx?file_no=i109"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49614-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T09:02:55Z","timestamp":1707555775000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49614-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031496134","9783031496141"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49614-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawai, HI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOA2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"117","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"62% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}