{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:09:33Z","timestamp":1775912973876,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"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":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188852","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"214-227","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["An almost-linear time algorithm for uniform random spanning tree generation"],"prefix":"10.1145","author":[{"given":"Aaron","family":"Schild","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873633"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403039"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89571"},{"key":"e_1_3_2_2_5_1","volume-title":"Modern graph theory","author":"Bollob\u00e1s B\u00e9la","year":"2013"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63516"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.07.011"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90016-3"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0014"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055499"},{"key":"e_1_3_2_2_12_1","volume-title":"Determinantpreserving sparsification of SDDM matrices with applications to counting and sampling spanning trees. CoRR, abs\/1705.00985","author":"Durfee David","year":"2017"},{"key":"e_1_3_2_2_13_1","volume-title":"Graph sparsification by edgeconnectivity and random spanning trees. CoRR, abs\/1005.0265","author":"Fung Wai Shing","year":"2010"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496834"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90022-6"},{"key":"e_1_3_2_2_17_1","first-page":"207","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201908","author":"Prahladh Harsha HHN","year":"2008"},{"key":"e_1_3_2_2_18_1","volume-title":"Springer Berlin Heidelberg","author":"Nicholas J.","year":"2016"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/andp.18471481202"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748019"},{"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.1145\/2488608.2488724"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90002-V"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316672815"},{"key":"e_1_3_2_2_27_1","volume-title":"Sparsified cholesky solvers for SDD linear systems. CoRR, abs\/1506.08204","author":"Lee Yin Tat","year":"2015"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722263"},{"key":"e_1_3_2_2_30_1","unstructured":"{Pro} Jim Propp. Personal communication with Aleksander Madry.  {Pro} Jim Propp. Personal communication with Aleksander Madry."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591832"},{"key":"e_1_3_2_2_32_1","volume-title":"An almost-linear time algorithm for uniform random spanning tree generation. CoRR, abs\/1711.06455","author":"Schild Aaron","year":"2017"},{"key":"e_1_3_2_2_33_1","volume-title":"Localization of electrical flows. CoRR, abs\/1708.01632","author":"Schild Aaron","year":"2017"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188852","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188852","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188852"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":35,"alternative-id":["10.1145\/3188745.3188852","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188852","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}