{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T16:47:22Z","timestamp":1776962842890,"version":"3.51.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    We show that the volume of a convex body in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {R}^{n}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    specified in the general membership oracle model can be computed to within relative error\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varepsilon \\gt 0\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    using\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(n^{3.5}\\psi ^{2} + n^3\/\\varepsilon ^{2})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    oracle queries, where\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\psi\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is the KLS constant. With the current bound of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\psi =\\widetilde{O}(1)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , this gives an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(n^{3.5} + n^3\/\\varepsilon ^{2})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    algorithm, improving on the Lov\u00e1sz-Vempala\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(n^{4}\/\\varepsilon ^{2})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    algorithm from 2003. The main new ingredient is an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(n^{3}\\psi ^{2})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    algorithm for isotropic transformation of a well-rounded convex body; we apply this iteratively to isotropize a general convex body. Following this, we can apply the\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(n^{3}\/\\varepsilon ^{2})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    volume algorithm of Cousins and Vempala for well-rounded convex bodies. We also give an efficient implementation of the new algorithm for convex polytopes defined by\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    inequalities in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {R}^{n}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    : polytope volume can be estimated in time\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(mn^{c+0.5}+mn^{c}\/\\varepsilon ^{2})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    where\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    &lt; 3.2 depends on the current matrix multiplication exponent and also improves on the previous best bound.\n                  <\/jats:p>","DOI":"10.1145\/3795687","type":"journal-article","created":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T20:23:56Z","timestamp":1770495836000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-4699-3895","authenticated-orcid":false,"given":"He","family":"Jia","sequence":"first","affiliation":[{"name":"Computer Science, Georgia Institute of Technology","place":["Atlanta, United States"]},{"name":"Computer Science, Northwestern University","place":["Atlanta, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9781-1402","authenticated-orcid":false,"given":"Aditi","family":"Laddha","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology","place":["Atlanta, United States"]},{"name":"Yale University","place":["Atlanta, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4692-5442","authenticated-orcid":false,"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"CSE, University of Washington","place":["Seattle, United States"]},{"name":"OpenAI Inc","place":["Seattle, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3779-433X","authenticated-orcid":false,"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[{"name":"Computer Science, Georgia Institute of Technology","place":["Atlanta, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,23]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-09-00650-X"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.63"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103439"},{"key":"e_1_3_3_5_2","article-title":"Complexity Term Balancer","author":"Brand Jan van den","unstructured":"Jan van den Brand. 2025. Complexity Term Balancer. www.ocf.berkeley.edu\/ vdbrand\/complexity\/.","journal-title":"www.ocf.berkeley.edu\/ vdbrand\/complexity\/"},{"key":"e_1_3_3_6_2","first-page":"1","article-title":"An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture","author":"Chen Yuansi","year":"2021","unstructured":"Yuansi Chen. 2021. An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture. Geometric and Functional Analysis 31, 1 (2021), 1\u201328.","journal-title":"Geometric and Functional Analysis"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746563"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054250"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/044\/1141926"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73043"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187701"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12176"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.133"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx052"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","unstructured":"Arun Jambulapati Yin Tat Lee and Santosh S. Vempala. 2022. A Slightly Improved Bound for the KLS Constant.DOI:10.48550\/ARXIV.2208.11644. Retrieved from https:\/\/arxiv.org\/abs\/2208.11644","DOI":"10.48550\/ARXIV.2208.11644"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451018"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574061"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/261619.261620"},{"key":"e_1_3_3_19_2","unstructured":"Bo\u2019az Klartag. 2023. Logarithmic bounds for isoperimetry and slices of convex sets. Ars Inveniendi Analytica (2023) Paper No. 4 17."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","unstructured":"Bo\u2019az Klartag and Joseph Lehec. 2022. Bourgain\u2019s slicing problem and KLS isoperimetry up to polylog.Geometric and Functional Analysis (GAFA). Springer 32 (2022) 1134\u20131159. DOI:10.48550\/ARXIV.2203.15551","DOI":"10.48550\/ARXIV.2203.15551"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","unstructured":"Yunbum Kook and Santosh S. Vempala. 2025. Sampling and integration of logconcave functions by algorithmic diffusion. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC\u201925). Association for Computing Machinery New York NY USA 924\u2013932.","DOI":"10.1145\/3717823.3718202"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","unstructured":"Yunbum Kook Santosh S. Vempala and Matthew S. Zhang. 2024. In-and-Out: Algorithmic diffusion for sampling convex bodies. In Proceedings of the 38th International Conference on Neural Information Processing Systems (NIPS\u201924). Curran Associates Inc. Red Hook NY USA. 37 Article 3440 108354\u2013108388.","DOI":"10.52202\/079017-3440"},{"key":"e_1_3_3_23_2","volume-title":"Proceedings of the IEEE FOCS","author":"Lee Yin Tat","year":"2017","unstructured":"Yin Tat Lee and Santosh Srinivas Vempala. 2017. Eldan\u2019s stochastic localization and the KLS hyperplane conjecture: An improved lower bound for expansion. In Proceedings of the IEEE FOCS."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188774"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2024.199.3.2"},{"key":"e_1_3_3_26_2","first-page":"138","article-title":"How to compute the volume?","author":"Lov\u00e1sz L.","year":"1990","unstructured":"L. Lov\u00e1sz. 1990. How to compute the volume? Jber. d. Dt. Math.-Verein, Jubil\u00e4umstagung 1990 (1990), 138\u2013151.","journal-title":"Jber. d. Dt. Math.-Verein, Jubil\u00e4umstagung 1990"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89553"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040402"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.08.004"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/1234700.1234701"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00082"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-006-0584-5"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOP760"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.134"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3795687","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T16:11:56Z","timestamp":1776960716000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3795687"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,23]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3795687"],"URL":"https:\/\/doi.org\/10.1145\/3795687","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,23]]},"assertion":[{"value":"2024-09-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}