{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,25]],"date-time":"2022-11-25T05:51:49Z","timestamp":1669355509098},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hasso-Plattner-Institut f\u00fcr Digital Engineering gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present fully polynomial time approximation schemes\nfor a broad class of Holant problems with complex edge weights, which\nwe call <jats:italic>Holant polynomials<\/jats:italic>. We transform these problems into partition\nfunctions of abstract combinatorial structures known as  <jats:italic>polymers<\/jats:italic>\nin statistical physics. Our method involves establishing zero-free regions\nfor the partition functions of polymer models and using the most\nsignificant terms of the <jats:italic>cluster expansion<\/jats:italic> to approximate them.\nResults of our technique include new approximation and sampling algorithms\nfor a diverse class of Holant polynomials in the low-temperature\nregime (i.e. small external field) and approximation algorithms for general\nHolant problems with small signature weights. Additionally, we\ngive randomised approximation and sampling algorithms with faster\nrunning times for more restrictive classes. Finally, we improve the\nknown zero-free regions for a perfect matching polynomial.<\/jats:p>","DOI":"10.1007\/s00037-022-00226-5","type":"journal-article","created":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T13:21:38Z","timestamp":1659360098000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Zeros and approximations of Holant polynomials on the complex plane"],"prefix":"10.1007","volume":"31","author":[{"given":"Katrin","family":"Casel","sequence":"first","affiliation":[]},{"given":"Philipp","family":"Fischbeck","sequence":"additional","affiliation":[]},{"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"G\u00f6bel","sequence":"additional","affiliation":[]},{"given":"J. A. Gregor","family":"Lagodzinski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"226_CR1","doi-asserted-by":"crossref","unstructured":"Giorgio Ausiello, Alberto Marchetti-Spaccamela, Pierluigi\nCrescenzi, Giorgio Gambosi, Marco Protasi & Viggo Kann\n(1999).  Complexity and approximation: combinatorial optimization\nproblems and their approximability properties. Springer. ISBN\n3540654313.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"#cr-split#-226_CR2.1","unstructured":"Miriam Backens (2018). A Complete Dichotomy for Complex-Valued"},{"key":"#cr-split#-226_CR2.2","doi-asserted-by":"crossref","unstructured":"Holantc. In Proceedings of ICALP 2018, 12:1-12:14.","DOI":"10.1016\/S0262-1762(19)30181-6"},{"key":"226_CR3","doi-asserted-by":"crossref","unstructured":"Alexander Barvinok & Guus Regts (2019). Weighted counting\nof solutions to sparse systems of equations. Combinatorics, Probability\nand Computing.  1\u201324","DOI":"10.1017\/S0963548319000105"},{"key":"226_CR4","doi-asserted-by":"crossref","unstructured":"Alexander I. Barvinok (2016a).  Combinatorics and Complexity\nof Partition Functions, volume 30 of Algorithms and combinatorics.\nSpringer.","DOI":"10.1007\/978-3-319-51829-9"},{"key":"226_CR5","doi-asserted-by":"crossref","unstructured":"Alexander I. Barvinok (2016b). Computing the Permanent of\n(Some) Complex Matrices. Foundations of Computational Mathematics\n16(2), 329\u2013342.","DOI":"10.1007\/s10208-014-9243-7"},{"key":"226_CR6","doi-asserted-by":"crossref","unstructured":"Alexander I. Barvinok (2019). Computing permanents of complex\ndiagonally dominant matrices and tensors. Israel Journal of Mathematics\n232(2), 931\u2013945.","DOI":"10.1007\/s11856-019-1896-0"},{"key":"226_CR7","doi-asserted-by":"crossref","unstructured":"Ivona\u00c1kov\u00c1, Andreas Galanis, Leslie Ann Goldberg &\nDaniel Stefankovic (2021). The Complexity of Approximating the\nMatching Polynomial in the Complex Plane. ACM Trans. Comput.\nTheory 13(2).","DOI":"10.1145\/3448645"},{"key":"226_CR8","doi-asserted-by":"crossref","unstructured":"Bla Bollobs (2006). The Art of Mathematics: Coffee Time in Memphis.\nCambridge University Press.","DOI":"10.1017\/CBO9780511816574"},{"key":"226_CR9","doi-asserted-by":"crossref","unstructured":"Christian Borgs, Jennifer T. Chayes, Jeff Kahn & L\u00c1szl\u00b4\u00d3\nLov\u00c1sz (2013). Left and right convergence of graphs with bounded\ndegree. Random Structures and Algorithms 42(1), 1\u201328.","DOI":"10.1002\/rsa.20414"},{"key":"226_CR10","unstructured":"Russ Bubley & Martin Dyer (1997). Graph Orientations with No\nSink and an Approximation for a Hard Case of #SAT. In Proceedings\nof SODA 1997, 248\u2013257."},{"key":"226_CR11","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Heng Guo & Tyson Williams (2016a). A Complete\nDichotomy Rises from the Capture of Vanishing Signatures. SIAM J.\nComput. 45(5), 1671\u20131728.","DOI":"10.1137\/15M1049798"},{"key":"226_CR12","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Heng Guo & Tyson Williams (2016b). The complexity\nof counting edge colorings and a dichotomy for some higher domain\nHolant problems. Research in the Mathematical Sciences 3(1), 1\u201377.","DOI":"10.1186\/s40687-016-0067-8"},{"key":"#cr-split#-226_CR13.1","unstructured":"Jin-Yi Cai & Tianyu Liu (2020). Counting Perfect Matchings and"},{"key":"#cr-split#-226_CR13.2","unstructured":"the Eight-Vertex Model. In Proceedings of ICALP 2020, 23:1-23:18."},{"key":"#cr-split#-226_CR14.1","unstructured":"Jin-Yi Cai, Tianyu Liu & Pinyan Lu (2019). Approximability of the"},{"key":"#cr-split#-226_CR14.2","unstructured":"Six-vertex Model. In Proceedings of SODA 2019, 2248-2261."},{"key":"226_CR15","doi-asserted-by":"crossref","unstructured":"Jin-yi Cai, Pinyan Lu & Mingji Xia (2011). Computational Complexity\nof Holant Problems. SIAM J. Comput. 40(4), 1101\u20131132.","DOI":"10.1137\/100814585"},{"key":"226_CR16","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2013). Dichotomy for Holant*\nProblems with Domain Size 3. In Proceedings of SODA 2013, 1278\u2013\n1295."},{"key":"#cr-split#-226_CR17.1","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2018). Dichotomy for Real"},{"key":"#cr-split#-226_CR17.2","unstructured":"Holantc Problems. In Proceedings of SODA 2018, 1802-1821."},{"key":"226_CR18","doi-asserted-by":"crossref","unstructured":"Sarah Cannon & Will Perkins (2020). Counting independent sets\nin unbalanced bipartite graphs. In Proceedings of SODA 2020, 1456\u2013\n1466.","DOI":"10.1137\/1.9781611975994.88"},{"key":"226_CR19","doi-asserted-by":"crossref","unstructured":"Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will\nPerkins, James Stewart & Eric Vigoda (2021). Fast Algorithms\nat Low Temperatures via Markov Chains. Random Structures & Algorithms\n58(2), 294\u2013321.","DOI":"10.1002\/rsa.20968"},{"key":"226_CR20","doi-asserted-by":"crossref","unstructured":"P\u00c9ter Csikv\u00c1 ri & Mohammad Reza Oboudi (2011). On the roots\nof edge cover polynomials of graphs. European Journal of Combinatorics\n32(8), 1407 \u2013 1416.","DOI":"10.1016\/j.ejc.2011.06.009"},{"key":"#cr-split#-226_CR21.1","unstructured":"Martin Dyer & Catherine Greenhill (1999). Random walks on"},{"key":"#cr-split#-226_CR21.2","unstructured":"combinatorial objects. In Surveys in Combinatorics 1999, 101-136."},{"key":"226_CR22","doi-asserted-by":"crossref","unstructured":"Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill\n& Mark Jerrum (2004). The Relative Complexity of Approximate\nCounting Problems. Algorithmica 38(3), 471\u2013500.","DOI":"10.1007\/s00453-003-1073-y"},{"key":"226_CR23","doi-asserted-by":"crossref","unstructured":"Sacha Friedli & Yvan Velenik (2017). Statistical Mechanics of\nLattice Systems: A Concrete Mathematical Introduction. Cambridge\nUniversity Press.","DOI":"10.1017\/9781316882603"},{"key":"226_CR24","doi-asserted-by":"crossref","unstructured":"Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda &\nLinji Yang (2014). Improved inapproximability results for counting\nindependent sets in the hard-core model. Random Structures and Algorithms\n45(1), 78\u2013110.","DOI":"10.1002\/rsa.20479"},{"key":"226_CR25","doi-asserted-by":"crossref","unstructured":"Christian Gruber & Herv\u00c9 Kunz (1971). General properties of\npolymer systems. Communications in Mathematical Physics 22(2),\n133\u2013161.","DOI":"10.1007\/BF01651334"},{"key":"226_CR26","doi-asserted-by":"crossref","unstructured":"Heng Guo, Chao Liao, Pinyan Lu & Chihao Zhang (2021). Zeros\nof Holant problems: locations and algorithms. ACM Trans. Algorithms\n17(1).","DOI":"10.1145\/3418056"},{"key":"226_CR27","doi-asserted-by":"crossref","unstructured":"Ole J. Heilmann & Elliott H. Lieb (1972). Theory of Monomer-\nDimer systems. Communications in Mathematical Physics 25(3), 190\u2013\n232.","DOI":"10.1007\/BF01877590"},{"key":"226_CR28","doi-asserted-by":"crossref","unstructured":"Tyler Helmuth, Will Perkins & Guus Regts (2019). Algorithmic\nPirogov-Sinai theory. In Proceedings of STOC 2019, 1009\u20131020. The referenced\nversion can be found at arxiv.org\/abs\/1806.11548.","DOI":"10.1145\/3313276.3316305"},{"key":"226_CR29","doi-asserted-by":"crossref","unstructured":"Lingxiao Huang, Pinyan Lu & Chihao Zhang (2016). Canonical\nPaths for MCMC: from Art to Science. In Proceedings of SODA 2016,\n514\u2013527.","DOI":"10.1137\/1.9781611974331.ch38"},{"key":"226_CR30","doi-asserted-by":"crossref","unstructured":"Matthew Jenssen, Peter Keevash & Will Perkins (2020). Algorithms\nfor #BIS-hard problems on expander graphs. SIAM Journal\non Computing 49(4), 681\u2013710.","DOI":"10.1137\/19M1286669"},{"key":"226_CR31","doi-asserted-by":"crossref","unstructured":"Mark Jerrum & Alistair Sinclair (1989). Approximating the Permanent.\nSIAM J. Comput. 18(6), 1149\u20131178.","DOI":"10.1137\/0218077"},{"key":"226_CR32","doi-asserted-by":"crossref","unstructured":"Mark Jerrum & Alistair Sinclair (1993). Polynomial-Time Approximation\nAlgorithms for the Ising Model. SIAM J. Comput. 22(5),\n1087\u20131116.","DOI":"10.1137\/0222066"},{"key":"226_CR33","doi-asserted-by":"crossref","unstructured":"Mark Jerrum, Leslie G. Valiant & Vijay V. Vazirani (1986).\nRandom Generation of Combinatorial Structures from a Uniform Distribution.\nTheoretical Computer Science 43(2-3), 169\u2013188.","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"226_CR34","doi-asserted-by":"crossref","unstructured":"Roman Koteck\u00dd & David Preiss (1986). Cluster expansion for\nabstract polymer models. Communications in Mathematical Physics\n103(3), 491\u2013498.","DOI":"10.1007\/BF01211762"},{"key":"226_CR35","unstructured":"Chao Liao, Jiabao Lin, Pinyan Lu & Zhenyu Mao (2019). Counting\nIndependent Sets and Colorings on Random Regular Bipartite\nGraphs. In Proceedings of APPROX\/RANDOM 2019, 34:1\u201334:12."},{"key":"226_CR36","unstructured":"Jiabao Lin & Hanpin Wang (2017). The Complexity of Holant Problems\nover Boolean Domain with Non-Negative Weights. In Proceedings\nof ICALP 2017, 29:1\u201329:14."},{"key":"#cr-split#-226_CR37.1","unstructured":"Jingcheng Liu, Pinyan Lu & Chihao Zhang (2014). FPTAS for"},{"key":"#cr-split#-226_CR37.2","doi-asserted-by":"crossref","unstructured":"Counting Weighted Edge Covers. In Proceedings of ESA 2014, 654-665.","DOI":"10.1007\/978-3-662-44777-2_54"},{"key":"226_CR38","doi-asserted-by":"crossref","unstructured":"Jingcheng Liu, Alistair Sinclair & Piyush Srivastava (2018).\nThe Ising Partition Function: Zeros and Deterministic Approximation.\nJournal of Statistical Physics 174(2), 287-315.","DOI":"10.1007\/s10955-018-2199-2"},{"key":"226_CR39","doi-asserted-by":"crossref","unstructured":"Pinyan Lu, Menghui Wang & Chihao Zhang (2014). FPTAS\nfor Weighted Fibonacci Gates and Its Applications. In Proceedings of\nICALP 2014, 787\u2013799.","DOI":"10.1007\/978-3-662-43948-7_65"},{"key":"226_CR40","doi-asserted-by":"crossref","unstructured":"Joseph E. Mayer & Elliott Montroll (1941). Molecular Distribution.\nThe Journal of Chemical Physics 9(1), 2\u201316.","DOI":"10.1063\/1.1750822"},{"key":"226_CR41","unstructured":"Colin McQuillan (2013). Approximating Holant problems by winding.\nCoRR arxiv.org\/abs\/1301.2880."},{"key":"226_CR42","doi-asserted-by":"crossref","unstructured":"Viresh Patel & Guus Regts (2017). Deterministic Polynomial-Time\nApproximation Algorithms for Partition Functions and Graph Polynomials.\nSIAM J. Comput. 46(6), 1893\u20131919.","DOI":"10.1137\/16M1101003"},{"key":"226_CR43","doi-asserted-by":"crossref","unstructured":"Han Peters & Guus Regts (2019). On a Conjecture of Sokal Concerning\nRoots of the Independence Polynomial. Michigan Mathematical\nJournal 68(1), 33\u201355.","DOI":"10.1307\/mmj\/1541667626"},{"key":"226_CR44","doi-asserted-by":"crossref","unstructured":"Guus Regts (2018). Zero-Free Regions of Partition Functions with\nApplications to Algorithms and Graph Limits. Combinatorica 38(4),\n987\u20131015.","DOI":"10.1007\/s00493-016-3506-7"},{"key":"226_CR45","doi-asserted-by":"crossref","unstructured":"Alistair Sinclair & Mark Jerrum (1989). Approximate Counting,\nUniform Generation and Rapidly Mixing Markov Chains. Information\nand Computation 82(1), 93\u2013133.","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"#cr-split#-226_CR46.1","doi-asserted-by":"crossref","unstructured":"Allan Sly (2010). Computational Transition at the Uniqueness","DOI":"10.1109\/FOCS.2010.34"},{"key":"#cr-split#-226_CR46.2","unstructured":"Threshold. In Proceedings of FOCS 2010, 287-296."},{"key":"226_CR47","unstructured":"Richard P. Stanley (1999). Enumerative Combinatorics, volume 2.\nCambridge University Press. ISBN 9781139811729 113981172X."},{"key":"226_CR48","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (2008). Holographic Algorithms. SIAM J. Comput.\n37(5), 1565\u20131594.","DOI":"10.1137\/070682575"},{"key":"#cr-split#-226_CR49.1","doi-asserted-by":"crossref","unstructured":"Dror Weitz (2006). Counting independent sets up to the tree threshold.","DOI":"10.1145\/1132516.1132538"},{"key":"#cr-split#-226_CR49.2","unstructured":"In Proceedings of STOC 2006, 140-149."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00226-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-022-00226-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00226-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T15:27:40Z","timestamp":1669303660000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-022-00226-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,27]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["226"],"URL":"https:\/\/doi.org\/10.1007\/s00037-022-00226-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,27]]},"assertion":[{"value":"27 July 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2022","order":2,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":3,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note.","order":4,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"11"}}