{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T16:59:16Z","timestamp":1782233956711,"version":"3.54.5"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T00:00:00Z","timestamp":1772236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T00:00:00Z","timestamp":1772236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NWO","award":["VI.Veni.222.303"],"award-info":[{"award-number":["VI.Veni.222.303"]}]},{"name":"NWO","award":["VI.Vidi.193.068"],"award-info":[{"award-number":["VI.Vidi.193.068"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2026,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Answering a question of Gamarnik and Smedira\u00a0[15], we give a polynomial time algorithm that approximately computes the volume of a truncation of a relaxation of the independent set polytope, improving on their quasi-polynomial time algorithm. Our algorithm is obtained by viewing the volume as an evaluation of a graph polynomial and we approximate this evaluation using Barvinok\u2019s interpolation method.<\/jats:p>","DOI":"10.1007\/s00454-026-00824-y","type":"journal-article","created":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T17:07:54Z","timestamp":1772298474000},"page":"508-525","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximating the Volume of a Truncated Relaxation of the Independence Polytope"],"prefix":"10.1007","volume":"76","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2554-5838","authenticated-orcid":false,"given":"Ferenc","family":"Bencs","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guus","family":"Regts","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,2,28]]},"reference":[{"key":"824_CR1","doi-asserted-by":"crossref","unstructured":"Anari, N., Liu, K., Gharan, S.O.: Spectral independence in high-dimensional expanders and applications to the hardcore model. SIAM J. Comput. 53(6), FOCS20\u20131\u2013FOCS20\u201337 (2024)","DOI":"10.1137\/20M1367696"},{"key":"824_CR2","doi-asserted-by":"crossref","unstructured":"Bandyopadhyay, A., Gamarnik, D.: Counting without sampling. New algorithms for enumeration problems using statistical physics, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 890\u2013899, (2006)","DOI":"10.1145\/1109557.1109655"},{"issue":"4","key":"824_CR3","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF02187886","volume":"2","author":"I B\u00e1r\u00e1ny","year":"1987","unstructured":"B\u00e1r\u00e1ny, I., F\u00fcredi, Z.: Computing the volume is difficult. Discrete Comput. Geom. 2(4), 319\u2013326 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"824_CR4","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1093\/imrn\/rnn133","volume":"2","author":"A Barvinok","year":"2009","unstructured":"Barvinok, A.: Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes. Int. Math. Res. Not. IMRN 2, 348\u2013385 (2009)","journal-title":"Int. Math. Res. Not. IMRN"},{"key":"824_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-51829-9","volume-title":"Combinatorics and complexity of partition functions, Algorithms and Combinatorics","author":"A Barvinok","year":"2016","unstructured":"Barvinok, A.: Combinatorics and complexity of partition functions, Algorithms and Combinatorics, vol. 30. Springer, Cham (2016)"},{"issue":"1","key":"824_CR6","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s11856-024-2615-z","volume":"262","author":"A Barvinok","year":"2024","unstructured":"Barvinok, A., Rudelson, M.: A quick estimate for the volume of a polyhedron. Israel J. Math. 262(1), 449\u2013473 (2024)","journal-title":"Israel J. Math."},{"key":"824_CR7","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1016\/j.jctb.2022.08.003","volume":"157","author":"F Bencs","year":"2022","unstructured":"Bencs, F., Csikv\u00e1ri, P.: Evaluations of Tutte polynomials of regular graphs. J. Combin. Theory Ser. B 157, 500\u2013523 (2022)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"824_CR8","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/s10955-010-9956-1","volume":"139","author":"R Bissacot","year":"2010","unstructured":"Bissacot, R., Fern\u00e1ndez, R., Procacci, A.: On the convergence of cluster expansions for polymer gases. J. Stat. Phys. 139(4), 598\u2013617 (2010)","journal-title":"J. Stat. Phys."},{"issue":"1","key":"824_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20414","volume":"42","author":"C Borgs","year":"2013","unstructured":"Borgs, C., Chayes, J., Kahn, J., Lov\u00e1sz, L.: Left and right convergence of graphs with bounded degree. Random Structures & Algorithms 42(1), 1\u201328 (2013)","journal-title":"Random Structures & Algorithms"},{"key":"824_CR10","doi-asserted-by":"crossref","unstructured":"Chen, Z., Liu, K., Vigoda, E.: Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion, Proceedings of the 53rd annual ACM SIGACT Symposium on Theory of Computing, pp. 1537\u20131550, (2021)","DOI":"10.1145\/3406325.3451035"},{"issue":"177","key":"824_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1090\/trans2\/177\/05","volume":"2","author":"RL Dobrushin","year":"1996","unstructured":"Dobrushin, R.L.: Estimates of semi-invariants for the Ising model at low temperatures. Translations of the American Mathematical Society-Series 2(177), 59\u201382 (1996)","journal-title":"Translations of the American Mathematical Society-Series"},{"issue":"1","key":"824_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. Assoc. Comput. Mach. 38(1), 1\u201317 (1991)","journal-title":"J. Assoc. Comput. Mach."},{"key":"824_CR13","unstructured":"Fadnavis, S.: On the roots of hypergraph chromatic polynomials, arXiv preprint arXiv:1509.05950 (2015)"},{"issue":"4","key":"824_CR14","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1017\/S0963548315000401","volume":"25","author":"A Galanis","year":"2016","unstructured":"Galanis, A., \u0160tefankovi\u010d, D., Vigoda, E.: Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Combin. Probab. Comput. 25(4), 500\u2013559 (2016)","journal-title":"Combin. Probab. Comput."},{"key":"824_CR15","unstructured":"Gamarnik, D., Smedira, D.: Computing the volume of a restricted independent set polytope deterministically, arXiv preprint arXiv:2312.03906 (2023)"},{"key":"824_CR16","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., Ramanan, K.: Uniqueness of Gibbs measures for continuous hardcore models. Ann. Probab. 47(4), 1949\u20131981 (2019)","DOI":"10.1214\/18-AOP1298"},{"key":"824_CR17","unstructured":"Gamarnik, D., Smedira, D.: Integrating high-dimensional functions deterministically, arXiv preprint arXiv:2402.08232 (2024)"},{"key":"824_CR18","unstructured":"Gritzmann, P., Klee, V.: Computational convexity, Handbook of discrete and computational geometry, pp. 937\u2013964, (2017)"},{"key":"824_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01651334","volume":"22","author":"C Gruber","year":"1971","unstructured":"Gruber, C., Kunz, H.: General properties of polymer systems. Comm. Math. Phys. 22, 133\u2013161 (1971)","journal-title":"Comm. Math. Phys."},{"key":"824_CR20","unstructured":"Guo, H., Vishvajeet N.: Deterministic approximation for the volume of the truncated fractional matching polytope, 16th Innovations in Theoretical Computer Science Conference, pp. Art. No. 57, 14, (2025)"},{"key":"824_CR21","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.jctb.2024.06.005","volume":"169","author":"M Jenssen","year":"2024","unstructured":"Jenssen, M., Patel, V., Regts, G.: Improved bounds for the zeros of the chromatic polynomial via Whitney\u2019s broken circuit theorem. J. Combin. Theory Ser. B 169, 233\u2013252 (2024)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"824_CR22","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/BF01211762","volume":"103","author":"R Koteck\u00fd","year":"1986","unstructured":"Koteck\u00fd, R., Preiss, D.: Cluster expansion for abstract polymer models. Comm. Math. Phys. 103(3), 491\u2013498 (1986)","journal-title":"Comm. Math. Phys."},{"issue":"195","key":"824_CR23","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1090\/S0025-5718-1991-1079024-2","volume":"57","author":"J Lawrence","year":"1991","unstructured":"Lawrence, J.: Polytope volume computation. Math. Comp. 57(195), 259\u2013271 (1991)","journal-title":"Math. Comp."},{"key":"824_CR24","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/060","volume-title":"Large networks and graph limits, American Mathematical Society Colloquium Publications","author":"L Lov\u00e1sz","year":"2012","unstructured":"Lov\u00e1sz, L.: Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60. American Mathematical Society, Providence, RI (2012)"},{"key":"824_CR25","first-page":"40","volume":"138","author":"V Patel","year":"2022","unstructured":"Patel, V., Regts, G.: Approximate counting using Taylor\u2019s theorem: a survey. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 138, 40\u201370 (2022)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"824_CR26","unstructured":"Penrose, O.: Convergence of fugacity expansions for classical systems. Statistical mechanics: foundations and applications 101, (1967)"},{"issue":"1","key":"824_CR27","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1307\/mmj\/1541667626","volume":"68","author":"H Peters","year":"2019","unstructured":"Peters, H., Regts, G.: On a conjecture of Sokal concerning roots of the independence polynomial. Michigan Math. J. 68(1), 33\u201355 (2019)","journal-title":"Michigan Math. J."},{"key":"824_CR28","unstructured":"Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency. Vol. A, Algorithms and Combinatorics, vol. 24,A, Springer-Verlag, Berlin, 2003. Paths, Flows, Matchings, Chapters 1\u201338"},{"issue":"6","key":"824_CR29","doi-asserted-by":"publisher","first-page":"2383","DOI":"10.1214\/13-AOP888","volume":"42","author":"A Sly","year":"2014","unstructured":"Sly, A., Sun, N.: Counting in two-spin models on d-regular graphs. Ann. Probab. 42(6), 2383\u20132416 (2014)","journal-title":"Ann. Probab."},{"issue":"6","key":"824_CR30","doi-asserted-by":"publisher","first-page":"1893","DOI":"10.1137\/16M1101003","volume":"46","author":"Viresh Patel and Guus Regts","year":"2017","unstructured":"Viresh Patel and Guus Regts: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46(6), 1893\u20131919 (2017)","journal-title":"SIAM J. Comput."},{"key":"824_CR31","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold, STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 140\u2013149, (2006)","DOI":"10.1145\/1132516.1132538"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-026-00824-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-026-00824-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-026-00824-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T16:40:58Z","timestamp":1782232858000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-026-00824-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,28]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["824"],"URL":"https:\/\/doi.org\/10.1007\/s00454-026-00824-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,28]]},"assertion":[{"value":"2 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}