{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T07:50:32Z","timestamp":1771573832581,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740425, CCF-1552097, DMS-1620014"],"award-info":[{"award-number":["CCF-1740425, CCF-1552097, DMS-1620014"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2429"],"award-info":[{"award-number":["N00014-17-1-2429"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316385","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":62,"title":["Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid"],"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"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_3_2_1_3_1","volume-title":"\u201cLog-Concave Polynomials III: Mason\u2019s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids\u201d. In: arXiv preprint arXiv:1811.01600","author":"Anari Nima","year":"2018","unstructured":"{Ana+18b} Nima Anari , Kuikui Liu , Shayan Oveis Gharan , and Cynthia Vinzant . \u201cLog-Concave Polynomials III: Mason\u2019s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids\u201d. In: arXiv preprint arXiv:1811.01600 ( 2018 ). {Ana+18b} Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. \u201cLog-Concave Polynomials III: Mason\u2019s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids\u201d. In: arXiv preprint arXiv:1811.01600 (2018)."},{"key":"e_1_3_2_1_4_1","first-page":"115","volume-title":"\u201cMonte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes","author":"Anari Nima","year":"2016","unstructured":"{AOR16} Nima Anari , Shayan Oveis Gharan , and Alireza Rezaei . \u201cMonte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes \u201d. In : COLT. 2016 , pp. 103\u2013 115 . {AOR16} Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. \u201cMonte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes\u201d. In: COLT. 2016, pp. 103\u2013115."},{"key":"e_1_3_2_1_5_1","volume-title":"FOCS. to appear.","author":"Anari Nima","year":"2018","unstructured":"{AOV18} Nima Anari , Shayan Oveis Gharan , and Cynthia Vinzant . \u201cLog-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids \u201d. In: FOCS. to appear. 2018 . {AOV18} Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. \u201cLog-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids\u201d. In: FOCS. to appear. 2018."},{"key":"e_1_3_2_1_6_1","unstructured":"{BH18} Petter Br\u00e4nd\u00e9n and June Huh. \u201cHodge-Riemann relations for Potts model partition functions\u201d. In: arXiv preprint arXiv:1811.01696 (2018).  {BH18} Petter Br\u00e4nd\u00e9n and June Huh. \u201cHodge-Riemann relations for Potts model partition functions\u201d. In: arXiv preprint arXiv:1811.01696 (2018)."},{"key":"e_1_3_2_1_7_1","unstructured":"{BH19} Petter Br\u00e4nd\u00e9n and June Huh. \u201cLorentzian polynomials\u201d. In: arXiv preprint arXiv:1902.03719 (2019).  {BH19} Petter Br\u00e4nd\u00e9n and June Huh. \u201cLorentzian polynomials\u201d. In: arXiv preprint arXiv:1902.03719 (2019)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-007-0008-8"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050022"},{"key":"e_1_3_2_1_10_1","unstructured":"{CTY15} Emma Cohen Prasad Tetali and Damir Yeliussizov. \u201cLattice path matroids: negative correlation and fast mixing\u201d. In: arXiv preprint arXiv:1505.06710 (2015).  {CTY15} Emma Cohen Prasad Tetali and Damir Yeliussizov. \u201cLattice path matroids: negative correlation and fast mixing\u201d. In: arXiv preprint arXiv:1505.06710 (2015)."},{"key":"e_1_3_2_1_11_1","first-page":"985","volume-title":"High Dimensional Expanders Imply Agreement Expanders","author":"Dinur I.","year":"2017","unstructured":"{DK17} I. Dinur and T. Kaufman . \u201c High Dimensional Expanders Imply Agreement Expanders \u201d. In : FOCS. 2017 , pp. 974\u2013 985 . {DK17} I. Dinur and T. Kaufman. \u201cHigh Dimensional Expanders Imply Agreement Expanders\u201d. In: FOCS. 2017, pp. 974\u2013985."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005980"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(72)90045-6"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129716"},{"key":"e_1_3_2_1_15_1","first-page":"342","volume-title":"International Symposium on Mathematical Foundations of Computer Science. Springer.","author":"Fortuin Cornelis Marius","year":"1999","unstructured":"{For72a} Cornelis Marius Fortuin . \u201c On the random-cluster model: II. The percolation model\u201d. In: Physica 58 (3 1972), pp. 393\u2013418. {For72b} Cornelis Marius Fortuin . \u201cOn the random-cluster model: III. The simple random-cluster model\u201d. In: Physica 59 (4 1972), pp. 545\u2013570. {Gam99} Anna Gambin. \u201cOn approximating the number of bases of exchange preserving matroids \u201d. In: International Symposium on Mathematical Foundations of Computer Science. Springer. 1999 , pp. 332\u2013 342 . {Gar73} H. Garland. \u201cp-adic curvature and the cohomology of discrete subgroups of p-adic groups\u201d. In: Annals of Mathematics 97.3 (1973), pp. 375\u2013423. {For72a} Cornelis Marius Fortuin. \u201cOn the random-cluster model: II. The percolation model\u201d. In: Physica 58 (3 1972), pp. 393\u2013418. {For72b} Cornelis Marius Fortuin. \u201cOn the random-cluster model: III. The simple random-cluster model\u201d. In: Physica 59 (4 1972), pp. 545\u2013570. {Gam99} Anna Gambin. \u201cOn approximating the number of bases of exchange preserving matroids\u201d. In: International Symposium on Mathematical Foundations of Computer Science. Springer. 1999, pp. 332\u2013342. {Gar73} H. Garland. \u201cp-adic curvature and the cohomology of discrete subgroups of p-adic groups\u201d. In: Annals of Mathematics 97.3 (1973), pp. 375\u2013423."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371660"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.04.005"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088330X"},{"key":"e_1_3_2_1_19_1","first-page":"1827","volume-title":"Random cluster dynamics for the Ising model is rapidly mixing","author":"Guo Heng","year":"2017","unstructured":"{GJ17} Heng Guo and Mark Jerrum . \u201c Random cluster dynamics for the Ising model is rapidly mixing \u201d. In : SODA. 2017 , pp. 1818\u2013 1827 . {GJ17} Heng Guo and Mark Jerrum. \u201cRandom cluster dynamics for the Ising model is rapidly mixing\u201d. In: SODA. 2017, pp. 1818\u20131827."},{"key":"e_1_3_2_1_20_1","first-page":"1","article-title":"A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability","volume":"68","author":"Guo Heng","year":"2018","unstructured":"{GJ18a} Heng Guo and Mark Jerrum . \u201c A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability \u201d. In: ICALP . 2018 , 68 : 1 \u2013 68 :12. {GJ18b} Heng Guo and Mark Jerrum. \u201cApproximately counting bases of bicircular matroids\u201d. 2018. {GJ18a} Heng Guo and Mark Jerrum. \u201cA Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability\u201d. In: ICALP. 2018, 68:1\u2013 68:12. {GJ18b} Heng Guo and Mark Jerrum. \u201cApproximately counting bases of bicircular matroids\u201d. 2018.","journal-title":"ICALP"},{"key":"e_1_3_2_1_21_1","volume-title":"The Random-Cluster Model","author":"Grimmett G. R","year":"2009","unstructured":"{Gri09} G. R Grimmett . The Random-Cluster Model . Berlin : Springer-Verlag , 2009 . {Gri09} G. R Grimmett. The Random-Cluster Model. Berlin: Springer-Verlag, 2009."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115966.3116118"},{"key":"e_1_3_2_1_23_1","volume-title":"Matrix analysis","author":"Horn Roger A","year":"2013","unstructured":"{HJ13} Roger A Horn and Charles R Johnson . Matrix analysis . 2 nd ed. Cambridge university press , 2013 . {HJ13} Roger A Horn and Charles R Johnson. Matrix analysis. 2nd ed. Cambridge university press, 2013.","edition":"2"},{"key":"e_1_3_2_1_24_1","unstructured":"{HW16} June Huh and Botong Wang. \u201cEnumeration of points lines planes etc\u201d. In: arXiv preprint arXiv:1609.05484 (2016).  {HW16} June Huh and Botong Wang. \u201cEnumeration of points lines planes etc\u201d. In: arXiv preprint arXiv:1609.05484 (2016)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000639"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0039-5"},{"key":"e_1_3_2_1_27_1","first-page":"729","volume-title":"Spectral gap and log-Sobolev constant for balanced matroids","author":"Jerrum Mark","year":"2002","unstructured":"{JS02} Mark Jerrum and Jung Bae Son . \u201c Spectral gap and log-Sobolev constant for balanced matroids \u201d. In : FOCS. 2002 , pp. 721\u2013 729 . {JS02} Mark Jerrum and Jung Bae Son. \u201cSpectral gap and log-Sobolev constant for balanced matroids\u201d. In: FOCS. 2002, pp. 721\u2013729."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"e_1_3_2_1_31_1","first-page":"1","article-title":"High Dimensional Random Walks and Colorful Expansion","volume":"4","author":"Kaufman Tali","year":"2017","unstructured":"{KM17} Tali Kaufman and David Mass . \u201c High Dimensional Random Walks and Colorful Expansion \u201d. In: ITCS . 2017 , 4 : 1 \u2013 4 :27. {KM17} Tali Kaufman and David Mass. \u201cHigh Dimensional Random Walks and Colorful Expansion\u201d. In: ITCS. 2017, 4:1\u20134:27.","journal-title":"ITCS"},{"key":"e_1_3_2_1_32_1","first-page":"1","article-title":"High Order Random Walks: Beyond Spectral Gap","volume":"47","author":"Kaufman Tali","year":"2018","unstructured":"{KO18} Tali Kaufman and Izhar Oppenheim . \u201c High Order Random Walks: Beyond Spectral Gap \u201d. In: APPROX\/RANDOM . 2018 , 47 : 1 \u2013 47 :17. {KO18} Tali Kaufman and Izhar Oppenheim. \u201cHigh Order Random Walks: Beyond Spectral Gap\u201d. In: APPROX\/RANDOM. 2018, 47:1\u201347:17.","journal-title":"APPROX\/RANDOM"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2481023"},{"key":"e_1_3_2_1_34_1","volume-title":"Connectivity Properties of Matroids. Tech. rep. EECS Department","author":"Mihail Milena","year":"1991","unstructured":"{MS91} Milena Mihail and Madhu Sudan . Connectivity Properties of Matroids. Tech. rep. EECS Department , University of California , Berkeley, Dec . 1991 . {MS91} Milena Mihail and Madhu Sudan. Connectivity Properties of Matroids. Tech. rep. EECS Department, University of California, Berkeley, Dec. 1991."},{"key":"e_1_3_2_1_35_1","article-title":"On the expansion of 0\/1 polytopes","author":"Mihail M.","year":"1989","unstructured":"{MV89} M. Mihail and U. Vazirani . \u201c On the expansion of 0\/1 polytopes \u201d. In: Journal of Combinatorial Theory. B ( 1989 ). {MV89} M. Mihail and U. Vazirani. \u201cOn the expansion of 0\/1 polytopes\u201d. In: Journal of Combinatorial Theory. B (1989).","journal-title":"Journal of Combinatorial Theory. B ("},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9948-x"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316385","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316385","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316385"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":36,"alternative-id":["10.1145\/3313276.3316385","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316385","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}