{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:54:35Z","timestamp":1752231275770,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T00:00:00Z","timestamp":1618790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["334828"],"award-info":[{"award-number":["334828"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1563757, CCF-1319987"],"award-info":[{"award-number":["CCF-1563757, CCF-1319987"]}],"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":[[2021,6,30]]},"abstract":"<jats:p>We study the problem of approximating the value of the matching polynomial on graphs with edge parameter\u00a0\u03b3, where\u00a0\u03b3 takes arbitrary values in the complex plane.<\/jats:p>\n          <jats:p>When \u03b3 is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of \u03b3, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree \u0394 as long as \u03b3 is not a negative real number less than or equal to \u22121\/(4(\u0394 \u22121)). Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all \u0394 \u2265 3 and all real\u00a0\u03b3 less than \u22121\/(4(\u0394 \u22121)), the problem of approximating the value of the matching polynomial on graphs of maximum degree \u0394 with edge parameter \u03b3 is #P-hard.<\/jats:p>\n          <jats:p>We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et\u00a0al. showed that for positive real \u03b3, it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is #P-hard on graphs with bounded connective constant for a dense set of\u00a0\u03b3 values on the negative real axis. Nevertheless, we show that the result does extend for any complex value \u03b3 that does not lie on the negative real axis. Our analysis accounts for complex values of\u00a0\u03b3 using geodesic distances in the complex plane in the metric defined by an appropriate density function.<\/jats:p>","DOI":"10.1145\/3448645","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:05:26Z","timestamp":1618877126000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["The Complexity of Approximating the Matching Polynomial in the Complex Plane"],"prefix":"10.1145","volume":"13","author":[{"given":"Ivona","family":"Bez\u00e1kov\u00e1","sequence":"first","affiliation":[{"name":"Rochester Institute of Technology, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Galanis","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9243-7"},{"volume-title":"Combinatorics and Complexity of Partition Functions","author":"Barvinok A.","key":"e_1_2_1_2_1","unstructured":"A. Barvinok . 2017. Combinatorics and Complexity of Partition Functions . Springer International . A. Barvinok. 2017. Combinatorics and Complexity of Partition Functions. Springer International."},{"volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC\u201907)","author":"Bayati M.","key":"e_1_2_1_3_1","unstructured":"M. Bayati , D. Gamarnik , D. A. Katz , C. Nair , and P. Tetali . 2007. Simple deterministic approximation algorithms for counting matchings . In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC\u201907) . 122--127. M. Bayati, D. Gamarnik, D. A. Katz, C. Nair, and P. Tetali. 2007. Simple deterministic approximation algorithms for counting matchings. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC\u201907). 122--127."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1184485"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"P. Buys A. Galanis V. Patel and G. Regts. 2020. Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs. arXiv:2006.14828  P. Buys A. Galanis V. Patel and G. Regts. 2020. Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs. arXiv:2006.14828","DOI":"10.1137\/1.9781611976465.91"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9626-6"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","author":"Galanis A.","year":"2017","unstructured":"A. Galanis , L. A. Goldberg , and D. \u0160tefankovi\u010d . 2017 . Inapproximability of the independent set polynomial below the Shearer threshold . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) . Article 28, 13 pages. arXiv:1612.05832 A. Galanis, L. A. Goldberg, and D. \u0160tefankovi\u010d. 2017. Inapproximability of the independent set polynomial below the Shearer threshold. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917). Article 28, 13 pages. arXiv:1612.05832"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190050310"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-017-0162-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088330X"},{"volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Harvey N. J. A.","key":"e_1_2_1_11_1","unstructured":"N. J. A. Harvey , P. Srivastava , and J. Vondr\u00e1k . 2018. Computing the independence polynomial: From the tree threshold down to the roots . In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918) . 1557--1576. N. J. A. Harvey, P. Srivastava, and J. Vondr\u00e1k. 2018. Computing the independence polynomial: From the tree threshold down to the roots. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918). 1557--1576."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01877590"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_14_1","unstructured":"D. Kraus and O. Roth. 2008. Conformal metrics. arXiv:0805.2235  D. Kraus and O. Roth. 2008. Conformal metrics. arXiv:0805.2235"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101003"},{"key":"e_1_2_1_16_1","unstructured":"H. Peters and G. Regts. 2017. On a conjecture of Sokal concerning roots of the independence polynomial. arxiv:1701.08049  H. Peters and G. Regts. 2017. On a conjecture of Sokal concerning roots of the independence polynomial. arxiv:1701.08049"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0708-2"},{"volume-title":"Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS\u201913)","author":"Sinclair A.","key":"e_1_2_1_18_1","unstructured":"A. Sinclair , P. Srivastava , and Y. Yin . 2013. Spatial mixing and approximation algorithms for graphs with bounded connective constant . In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS\u201913) . 300--309. A. Sinclair, P. Srivastava, and Y. Yin. 2013. Spatial mixing and approximation algorithms for graphs with bounded connective constant. In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS\u201913). 300--309."},{"key":"e_1_2_1_19_1","volume-title":"Phase transitions in the complex plane of physical parameters. Nature Scientific Reports 4","author":"Wei B.-B.","year":"2014","unstructured":"B.-B. Wei , S.-W. Chen , H.-C. Po , and R.-B. Liu . 2014. Phase transitions in the complex plane of physical parameters. Nature Scientific Reports 4 ( 2014 ), Article 5202. B.-B. Wei, S.-W. Chen, H.-C. Po, and R.-B. Liu. 2014. Phase transitions in the complex plane of physical parameters. Nature Scientific Reports 4 (2014), Article 5202."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448645","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448645","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448645","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:43Z","timestamp":1750193263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448645"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,19]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3448645"],"URL":"https:\/\/doi.org\/10.1145\/3448645","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,4,19]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}