{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T07:17:15Z","timestamp":1790061435534,"version":"4.0.1"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"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":["1065125"],"award-info":[{"award-number":["1065125"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ONR Award","award":["N00014-16-1-2374"],"award-info":[{"award-number":["N00014-16-1-2374"]}]},{"name":"National Science Foundation Graduate Research Fellowship","award":["1122374"],"award-info":[{"award-number":["1122374"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055499","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T16:27:45Z","timestamp":1497544065000},"page":"730-742","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Sampling random spanning trees faster than matrix multiplication"],"prefix":"10.1145","author":[{"given":"David","family":"Durfee","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Kyng","sequence":"additional","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Peebles","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anup B.","family":"Rao","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[{"name":"Google, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403039"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873633"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63516"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90016-3"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0014"},{"key":"e_1_3_2_2_7_1","unstructured":"Shayan Oveis Gharan Amin Saberi and Mohit Singh. 2011.  Shayan Oveis Gharan Amin Saberi and Mohit Singh. 2011."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"e_1_3_2_2_9_1","unstructured":"Navin Goyal Luis Rademacher and Santosh Vempala. 2009.  Navin Goyal Luis Rademacher and Santosh Vempala. 2009."},{"key":"e_1_3_2_2_10_1","volume-title":"Random Spanning Trees. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909)","author":"Expanders"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90022-6"},{"key":"e_1_3_2_2_12_1","volume-title":"LATIN 2016: Theoretical Informatics","volume":"9644","author":"Nicholas J."},{"key":"e_1_3_2_2_13_1","unstructured":"522\u2013535.  522\u2013535."},{"key":"e_1_3_2_2_14_1","unstructured":"Roger A Horn and Charles R Johnson. 2012.  Roger A Horn and Charles R Johnson. 2012."},{"key":"e_1_3_2_2_15_1","unstructured":"Matrix analysis. Cambridge university press.  Matrix analysis. Cambridge university press."},{"key":"e_1_3_2_2_16_1","unstructured":"Jonathan Kelner and Aleksander Madry. 2009.  Jonathan Kelner and Aleksander Madry. 2009."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748019"},{"key":"e_1_3_2_2_18_1","unstructured":"Jonathan A. Kelner Lorenzo Orecchia Aaron Sidford and Zeyuan Allen Zhu. 2013.  Jonathan A. Kelner Lorenzo Orecchia Aaron Sidford and Zeyuan Allen Zhu. 2013."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_2_20_1","unstructured":"Gustav Kirchhoff. 1847.  Gustav Kirchhoff. 1847."},{"key":"e_1_3_2_2_21_1","unstructured":"\u00dc ber die Aufl \u00f6sung der Gliechungen auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str \u00f6me gef \u00fchrt wird. In Poggendorgs Ann. Phys. Chem. 497\u2013508.  \u00dc ber die Aufl \u00f6sung der Gliechungen auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str \u00f6me gef \u00fchrt wird. In Poggendorgs Ann. Phys. Chem. 497\u2013508."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90002-V"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"e_1_3_2_2_26_1","unstructured":"Rasmus Kyng and Sushant Sachdeva. 2016.  Rasmus Kyng and Sushant Sachdeva. 2016."},{"key":"e_1_3_2_2_27_1","volume-title":"Simple. In Proceedings of the 57th annual Symposium on Foundations of Computer Science, FOCS 2016.","author":"Fast Approximate Gaussian"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.24"},{"key":"e_1_3_2_2_29_1","unstructured":"Russell Lyons and Yuval Peres. 2016.  Russell Lyons and Yuval Peres. 2016."},{"key":"e_1_3_2_2_30_1","unstructured":"Probability on trees and networks. Vol. 42. Cambridge University Press.  Probability on trees and networks. Vol. 42. Cambridge University Press."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722263"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_2_34_1","unstructured":"Virginia Vassilevska Williams. 2012.  Virginia Vassilevska Williams. 2012."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055499","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055499","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:36:20Z","timestamp":1750203380000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":34,"alternative-id":["10.1145\/3055399.3055499","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055499","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}