{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T09:05:12Z","timestamp":1695287112948},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T00:00:00Z","timestamp":1490313600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00493-016-3506-7","type":"journal-article","created":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T10:10:55Z","timestamp":1490350255000},"page":"987-1015","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Zero-Free Regions of Partition Functions with Applications to Algorithms and Graph Limits"],"prefix":"10.1007","volume":"38","author":[{"given":"Guus","family":"Regts","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,24]]},"reference":[{"key":"3506_CR1","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s00493-014-3066-7","volume":"35","author":"M. Ab\u00e9rt","year":"2015","unstructured":"M. Ab\u00e9rt and T. Hubai: Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs, Combinatorica 35 (2015), 127\u2013151.","journal-title":"Combinatorica"},{"key":"3506_CR2","doi-asserted-by":"publisher","first-page":"3089","DOI":"10.1137\/080739379","volume":"39","author":"I. Arad","year":"2010","unstructured":"I. Arad and Z. Landau: Quantum computation and the evaluation of tensor networks, SIAM Journal on Computing 39 (2010), 3089\u20133121.","journal-title":"SIAM Journal on Computing"},{"key":"3506_CR3","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1145\/1250790.1250809","volume-title":"Proceedings of the thirty-ninth annual ACM symposium on Theory of computing","author":"M. Bayati","year":"2007","unstructured":"M. Bayati, D. Gamarnik, D. Katz, C. Nair and P. Tetali: Simple deterministic approximation algorithms for counting matchings, in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing 122\u2013127, ACM, 2007."},{"key":"3506_CR4","first-page":"1","volume-title":"Foundations of Computational Mathematics","author":"A. Barvinok","year":"2014","unstructured":"A. Barvinok: Computing the permanent of (some) complex matrices, Foundations of Computational Mathematics (2014), 1\u201314."},{"key":"3506_CR5","doi-asserted-by":"publisher","first-page":"339","DOI":"10.4086\/toc.2015.v011a013","volume":"11","author":"A. Barvinok","year":"2015","unstructured":"A. Barvinok: Computing the partition function for cliques in a graph, Theory of Computing 11 (2015), 339\u2013355.","journal-title":"Theory of Computing"},{"key":"3506_CR6","volume-title":"Computing the partition function of a polynomial on the Boolean cube","author":"A. Barvinok","year":"2015","unstructured":"A. Barvinok: Computing the partition function of a polynomial on the Boolean cube, arXiv preprint, arXiv:1503.07463 (2015)."},{"key":"3506_CR7","doi-asserted-by":"crossref","unstructured":"A. Barvinok: Approximating permanents and hafnians, Discrete Analysis 2 (2017).","DOI":"10.19086\/da.1244"},{"key":"3506_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00493-015-3024-z","volume":"36","author":"A. Barvinok","year":"2016","unstructured":"A. Barvinok and P. Sober\u00f3n: Computing the partition function for graph homomorphisms, Combinatorica 36 (2016), 1\u201318.","journal-title":"Combinatorica"},{"key":"3506_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcta.2015.08.001","volume":"137","author":"A. Barvinok","year":"2016","unstructured":"A. Barvinok and P. Sober\u00f3n: Computing the partition function for graph homomorphisms with multiplicities, Journal of Combinatorial Theory, Series A 137 (2016), 1\u201326.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"3506_CR10","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-1-4419-9675-6_15","volume-title":"Selected Works of Oded Schramm","author":"I. Benjamini","year":"2011","unstructured":"I. Benjamini and O. Schramm: Recurrence of distributional limits of finite planar graphs, in: Selected Works of Oded Schramm, 533\u2013545, Springer New York, 2011."},{"key":"3506_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20414","volume":"42","author":"C. Borgs","year":"2013","unstructured":"C. Borgs, J. Chayes, J. Kahn and L. Lov\u00e1sz: Left and right convergence of graphs with bounded degree, Random Structures and Algorithms 42 (2013), 1\u201328.","journal-title":"Random Structures and Algorithms"},{"key":"3506_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1137\/S0097539798338175","volume":"29","author":"R. Bubley","year":"1999","unstructured":"R. Bubley, M. Dyer, C. Greenhill and M. Jerrum: On approximately counting colorings of small degree graphs, SIAM Journal on Computing 29 (1999), 387\u2013400.","journal-title":"SIAM Journal on Computing"},{"key":"3506_CR13","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"A. Bulatov","year":"2005","unstructured":"A. Bulatov and M. Grohe: The complexity of partition functions, Theoretical Computer Science 348 (2005), 148\u2013186.","journal-title":"Theoretical Computer Science"},{"key":"3506_CR14","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/110840194","volume":"42","author":"J. Cai","year":"2013","unstructured":"J. Cai, X. Chen and P. Lu: Graph homomorphisms with complex values: A dichotomy theorem, SIAM Journal on Computing 42 (2013), 924\u20131029.","journal-title":"SIAM Journal on Computing"},{"key":"3506_CR15","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1145\/2488608.2488687","volume-title":"Proceedings of the forty-fifth annual ACM symposium on Theory of computing","author":"J. Cai","year":"2013","unstructured":"J. Cai, H. Guo and T. Williams: A complete dichotomy rises from the capture of vanishing signatures, in: Proceedings of the forty-fifth annual ACM symposium on Theory of computing, 635\u2013644. ACM, 2013."},{"key":"3506_CR16","first-page":"253","volume-title":"ISAAC","author":"J. Cai","year":"2010","unstructured":"J. Cai, S. Huang and P. L: From Holant to #CSP and Back: Dichotomy for Holantc Problems, in: ISAAC, 253\u2013265, 2010."},{"key":"3506_CR17","first-page":"715","volume-title":"Proceedings of the 41st annual ACM symposium on Theory of computing","author":"J. Cai","year":"2009","unstructured":"J. Cai, P. Lu and M. Xia: Holant problems and counting CSP, in: Proceedings of the 41st annual ACM symposium on Theory of computing, STOC 09, 715\u2013724, New York, NY, USA, 2009."},{"key":"3506_CR18","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1137\/100814585","volume":"40","author":"J. Cai","year":"2011","unstructured":"J. Cai, P. Lu and M. Xia: Computational complexity of Holant problems, SIAM Journal on Computing 40 (2011), 1101\u20131132.","journal-title":"SIAM Journal on Computing"},{"key":"3506_CR19","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/j.ejc.2015.07.009","volume":"52","author":"P. Csikv\u00e1ri","year":"2016","unstructured":"P. Csikv\u00e1ri and P. E. Frenkel: Benjamini\u2013Schramm continuity of root moments of graph polynomials, European Journal of Combinatorics 52 (2016), 302\u2013320.","journal-title":"European Journal of Combinatorics"},{"key":"3506_CR20","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1006\/jctb.1993.1017","volume":"57","author":"P. Harpe de la","year":"1993","unstructured":"P. de la Harpe and V.F.R. Jones: Graph invariants related to statistical mechanical models: examples and problems, Journal of Combinatorial Theory, Series B 57 (1993), 207\u2013227.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"3506_CR21","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.jalgebra.2011.10.030","volume":"350","author":"J. Draisma","year":"2012","unstructured":"J. Draisma, D. Gijswijt, L. Lov\u00e1sz, G. Regts and A. Schrijver: Characterizing partition functions of the vertex model, Journal of Algebra 350 (2012), 197\u2013206.","journal-title":"Journal of Algebra"},{"key":"3506_CR22","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"M. Dyer","year":"2000","unstructured":"M. Dyer and C. Greenhill: The complexity of counting graph homomorphisms, Random Structures and Algorithms 17 (2000), 260\u2013289.","journal-title":"Random Structures and Algorithms"},{"key":"3506_CR23","first-page":"677","volume-title":"Ferromagnetic Potts model: Refined #BIS-hardness and related results","author":"A. Galanis","year":"2014","unstructured":"A. Galanis, D. Stefankovic, E. Vigoda and L. Yang: Ferromagnetic Potts model: Refined #BIS-hardness and related results, in: RANDOM 2014, LNCS 6845, 677\u2013691 2014. Full version available at arXiv:1311.4839."},{"key":"3506_CR24","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.jda.2010.10.002","volume":"12","author":"D. Gamarnik","year":"2012","unstructured":"D. Gamarnik and D. Katz: Correlation decay and deterministic FPTAS for counting list-colorings of a graph, Journal of Discrete Algorithms 12 (2012), 29\u201347.","journal-title":"Journal of Discrete Algorithms"},{"key":"3506_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2371656.2371660","volume":"59","author":"L. A. Goldberg","year":"2012","unstructured":"L. A. Goldberg and M. Jerrum: Approximating the partition function of the ferromagnetic Potts model, Journal of the ACM 59 (2012), 1\u201325.","journal-title":"Journal of the ACM"},{"key":"3506_CR26","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.jcss.2014.06.007","volume":"81","author":"L. A. Goldberg","year":"2015","unstructured":"L. A. Goldberg, M. Jerrum and C. McQuillan: Approximating the partition function of planar two-state spin systems, Journal of Computer and System Sciences 81 (2015), 330\u2013358.","journal-title":"Journal of Computer and System Sciences"},{"key":"3506_CR27","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.jctb.2012.08.002","volume":"103","author":"B. Jackson","year":"2013","unstructured":"B. Jackson, A. Procacci and A. D. Sokal: Complex zero-free regions at large jqj for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights, Journal of Combinatorial Theory, Series B 103 (2013), 21\u201345.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"3506_CR28","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1103\/PhysRev.87.410","volume":"87","author":"T. Lee","year":"1952","unstructured":"T. Lee and T. Yang: Statistical theory of equations of state and phase transitions. I. Theory of condensation, Physical Review 87 (1952), 404.","journal-title":"Physical Review"},{"key":"3506_CR29","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz: Large Networks and Graph Limits, Vol. 60, American Mathematical Society, Providence, Rhode Island, 2012.","DOI":"10.1090\/coll\/060"},{"key":"3506_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejc.2015.10.009","volume":"53","author":"L.M. Lov\u00e1sz","year":"2016","unstructured":"L.M. Lov\u00e1sz: A short proof of the equivalence of left and right convergence for sparse graphs, European Journal of Combinatorics 53 (2016), 1\u20137.","journal-title":"European Journal of Combinatorics"},{"key":"3506_CR31","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/978-3-642-40328-6_44","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"P. Lu","year":"2013","unstructured":"P. Lu and Y. Yin: Improved FPTAS for multi-spin systems, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 639\u2013654, Springer Berlin Heidelberg, 2013."},{"key":"3506_CR32","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/050644756","volume":"38","author":"I. L. Markov","year":"2008","unstructured":"I. L. Markov and Y. Shi: Simulating quantum computation by contracting tensor networks, SIAM Journal on Computing 38 (2008), 963\u2013981.","journal-title":"SIAM Journal on Computing"},{"key":"3506_CR33","unstructured":"V. Patel and G. Regts: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, arXiv preprint arXiv:1607.01167, 2016."},{"key":"3506_CR34","volume-title":"Graph Parameters and Invariants of the Orthogonal Group","author":"G. Regts","year":"2013","unstructured":"G. Regts: Graph Parameters and Invariants of the Orthogonal Group, PhD thesis, University of Amsterdam, 2013."},{"key":"3506_CR35","first-page":"1151","volume":"118","author":"A. D. Scott","year":"2005","unstructured":"A. D. Scott and A. D. Sokal: The repulsive lattice gas, the independent-set polynomial, and the Lov\u00e1sz local lemma, Journal of Statistical Physics 118 (2005), 1151\u20131261.","journal-title":"the independent-set polynomial, and the Lov\u00e1sz local lemma, Journal of Statistical Physics"},{"key":"3506_CR36","doi-asserted-by":"publisher","first-page":"666","DOI":"10.1007\/s10955-014-0947-5","volume":"155","author":"A. Sinclair","year":"2014","unstructured":"A. Sinclair, P. Srivastava and M. Thurley: Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs, Journal of Statistical Physics 155 (2014), 666\u2013686.","journal-title":"Journal of Statistical Physics"},{"key":"3506_CR37","first-page":"361","volume-title":"Proceedings of the 53rd Annual Symposium on Foundations of Computer Science","author":"A. Sly","year":"2012","unstructured":"A. Sly and N. Sun: The computational hardness of counting in two-spin models on d-regular graphs, in: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), 2012 IEEE, 361\u2013369. IEEE, 2012."},{"key":"3506_CR38","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1090\/S0894-0347-07-00568-1","volume":"20","author":"B. Szegedy","year":"2007","unstructured":"B. Szegedy: Edge-coloring models and re ection positivity, Journal of the American Mathematical Society 20 (2007), 969\u2013988.","journal-title":"Journal of the American Mathematical Society"},{"key":"3506_CR39","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-642-13580-4_12","volume-title":"Fete of Combinatorics and Computer Science","author":"B. Szegedy","year":"2010","unstructured":"B. Szegedy: Edge coloring models as singular vertex-coloring models, in: Fete of Combinatorics and Computer Science (G. O. H. Katona, A. Schrijver, T. Szonyi, editors), Springer, Heidelberg and J\u00e1nos Bolyai Mathematical Society, Budapest (2010), 327\u2013336."},{"key":"3506_CR40","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1145\/1132516.1132538","volume-title":"Proceedings of the thirty-eighth annual ACM symposium on Theory of computing","author":"D. Weitz","year":"2006","unstructured":"D. Weitz: Counting independent sets up to the tree threshold, in: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, STOC 06, 140\u2013149, New York, NY, USA, 2006. ACM."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-016-3506-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3506-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3506-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,26]],"date-time":"2022-07-26T21:20:25Z","timestamp":1658870425000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-016-3506-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,24]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["3506"],"URL":"https:\/\/doi.org\/10.1007\/s00493-016-3506-7","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,24]]},"assertion":[{"value":"2 March 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}