{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T15:48:57Z","timestamp":1773935337395,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451091","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"408-420","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests"],"prefix":"10.1145","author":[{"given":"Nima","family":"Anari","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Kuikui","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}]},{"given":"Shayan Oveis","family":"Gharan","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}]},{"given":"Cynthia","family":"Vinzant","sequence":"additional","affiliation":[{"name":"North Carolina State University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0271-9687","authenticated-orcid":false,"given":"Thuy-Duong","family":"Vuong","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(80)90017-1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2018.188.2.1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403039"},{"key":"e_1_3_2_1_4_1","volume-title":"Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases. ArXiv, abs\/2004.09079","author":"Anari Nima","year":"2020","unstructured":"Nima Anari and Michal Derezinski. 2020. Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases. ArXiv, abs\/2004.09079, 2020."},{"key":"e_1_3_2_1_5_1","volume-title":"Shayan Oveis Gharan, and Cynthia Vinzant","author":"Anari Nima","year":"2018","unstructured":"Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. 2018. Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids. CoRR, abs\/1811.01600, 2018."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316385"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs.2018.00013"},{"key":"e_1_3_2_1_8_1","first-page":"2","article-title":"Negative dependence and the geometry of polynomials","volume":"22","author":"Borcea Julius","year":"2009","unstructured":"Julius Borcea, Petter Br\u00e4nd\u00e9n, and Thomas Liggett. 2009. Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22, 2, 2009. Pages 521\u2013567.","journal-title":"Journal of the American Mathematical Society"},{"key":"e_1_3_2_1_9_1","volume-title":"Hodge-Riemann relations for Potts model partition functions. arXiv preprint arXiv:1811.01696","author":"Br\u00e4nd\u00e9n Petter","year":"2018","unstructured":"Petter Br\u00e4nd\u00e9n and June Huh. 2018. Hodge-Riemann relations for Potts model partition functions. arXiv preprint arXiv:1811.01696, 2018."},{"key":"e_1_3_2_1_10_1","volume-title":"Lorentzian polynomials. arXiv preprint arXiv:1902.03719","author":"Br\u00e4nd\u00e9n Petter","year":"2019","unstructured":"Petter Br\u00e4nd\u00e9n and June Huh. 2019. Lorentzian polynomials. arXiv preprint arXiv:1902.03719, 2019."},{"key":"e_1_3_2_1_11_1","first-page":"442","article-title":"Generating random spanning trees","author":"Broder Andrei Z","year":"1989","unstructured":"Andrei Z Broder. 1989. Generating random spanning trees. In FOCS. 89, Pages 442\u2013447.","journal-title":"FOCS. 89, Pages"},{"key":"e_1_3_2_1_12_1","volume-title":"Exponential Inapproximability of Selecting a Maximum","author":"Civril Ali","year":"2010","unstructured":"Ali \\c Civril and Malik Magdon-Ismail. 2010. Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix. CoRR, abs\/1006.4349, 2010. arxiv:1006.4349"},{"key":"e_1_3_2_1_13_1","first-page":"153","volume-title":"Congressus Numerantium, 202","author":"Cloteaux Brian","year":"2010","unstructured":"Brian Cloteaux. 2010. Approximating the number of bases for almost all matroids. Congressus Numerantium, 202, 2010. Pages 149\u2013153."},{"key":"e_1_3_2_1_14_1","volume-title":"Lattice path matroids: negative correlation and fast mixing. arXiv preprint arXiv:1505.06710","author":"Cohen Emma","year":"2015","unstructured":"Emma Cohen, Prasad Tetali, and Damir Yeliussizov. 2015. Lattice path matroids: negative correlation and fast mixing. arXiv preprint arXiv:1505.06710, 2015."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0014"},{"key":"e_1_3_2_1_16_1","volume-title":"Elements of information theory","author":"Cover Thomas M","unstructured":"Thomas M Cover and Joy A Thomas. 2012. Elements of information theory. John Wiley & Sons."},{"key":"e_1_3_2_1_17_1","volume-title":"Modified log-Sobolev inequalities for strongly log-concave distributions. arXiv preprint arXiv:1903.06081","author":"Cryan Mary","year":"2019","unstructured":"Mary Cryan, Heng Guo, and Giorgos Mousa. 2019. Modified log-Sobolev inequalities for strongly log-concave distributions. arXiv preprint arXiv:1903.06081, 2019."},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Pages 315\u2013323","author":"Summa Marco Di","year":"2014","unstructured":"Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, and Carsten Moldenhauer. 2014. On largest volume simplices and sub-determinants. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Pages 315\u2013323."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.94"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055499"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.90"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129716"},{"key":"e_1_3_2_1_23_1","volume-title":"Theory of optimal experiments","author":"Fedorov Valerii Vadimovich","unstructured":"Valerii Vadimovich Fedorov. 2013. Theory of optimal experiments. Elsevier."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48340-3_30"},{"key":"e_1_3_2_1_25_1","unstructured":"Ashish Goel Sanjeev Khanna Sharath Raghvendra and Hongyang Zhang. [n.d.]. Connectivity in Random Forests and Credit Networks."},{"key":"e_1_3_2_1_26_1","volume-title":"Approximately counting bases of bicircular matroids. arXiv preprint arXiv:1808.09548","author":"Guo Heng","year":"2018","unstructured":"Heng Guo and Mark Jerrum. 2018. Approximately counting bases of bicircular matroids. arXiv preprint arXiv:1808.09548, 2018."},{"key":"e_1_3_2_1_27_1","volume-title":"Advances in combinatorial mathematics","author":"Gurvits Leonid","unstructured":"Leonid Gurvits. 2009. On multivariate Newton-like inequalities. In Advances in combinatorial mathematics. Springer. Pages 61\u201378."},{"key":"e_1_3_2_1_28_1","first-page":"6","article-title":"Two remarks concerning balanced matroids","volume":"26","author":"Jerrum Mark","year":"2006","unstructured":"Mark Jerrum. 2006. Two remarks concerning balanced matroids. Combinatorica, 26, 6, 2006. Pages 733\u2013742.","journal-title":"Combinatorica"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181997"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000639"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_2_1_32_1","volume-title":"On sampling and greedy map inference of constrained determinantal point processes. arXiv preprint arXiv:1607.01551","author":"Kathuria Tarun","year":"2016","unstructured":"Tarun Kathuria and Amit Deshpande. 2016. On sampling and greedy map inference of constrained determinantal point processes. arXiv preprint arXiv:1607.01551, 2016."},{"key":"e_1_3_2_1_33_1","volume-title":"High dimensional random walks and colorful expansion. arXiv preprint arXiv:1604.02947","author":"Kaufman Tali","year":"2016","unstructured":"Tali Kaufman and David Mass. 2016. High dimensional random walks and colorful expansion. arXiv preprint arXiv:1604.02947, 2016."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3847-0"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.75"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1995.1005"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2481023"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Pages 2019\u20132036","author":"Madry Aleksander","year":"2014","unstructured":"Aleksander Madry, Damian Straszak, and Jakub Tarnawski. 2014. Fast generation of random spanning trees and the effective resistance metric. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Pages 2019\u20132036."},{"key":"e_1_3_2_1_39_1","volume-title":"Journal of Combinatorial Theory","author":"Mihail M.","year":"1989","unstructured":"M. Mihail and U. Vazirani. 1989. On the expansion of 0\/1 polytopes. Journal of Combinatorial Theory, 1989."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000003"},{"key":"e_1_3_2_1_41_1","volume-title":"M-convex function on generalized polymatroid. Mathematics of operations research, 24, 1","author":"Murota Kazuo","year":"1999","unstructured":"Kazuo Murota and Akiyoshi Shioura. 1999. M-convex function on generalized polymatroid. Mathematics of operations research, 24, 1, 1999. Pages 95\u2013105."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13160-017-0285-5"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746628"},{"key":"e_1_3_2_1_44_1","volume-title":"A Polynomial Time MCMC Method for Sampling from Continuous DPPs. arXiv preprint arXiv:1810.08867","author":"Gharan Shayan Oveis","year":"2018","unstructured":"Shayan Oveis Gharan and Alireza Rezaei. 2018. A Polynomial Time MCMC Method for Sampling from Continuous DPPs. arXiv preprint arXiv:1810.08867, 2018."},{"key":"e_1_3_2_1_45_1","volume-title":"Matroid theory. 3","author":"Oxley James G","unstructured":"James G Oxley. 2006. Matroid theory. 3, Oxford University Press, USA."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00226-9"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.3390\/a11040053"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188852"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_50_1","unstructured":"David G. Wagner. 2009. Multivariate stable polynomials: theory and applications."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451091","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":51,"alternative-id":["10.1145\/3406325.3451091","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451091","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}