{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:45Z","timestamp":1787340225860,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1122374"],"award-info":[{"award-number":["1122374"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1563838"],"award-info":[{"award-number":["CCF-1563838"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1718533"],"award-info":[{"award-number":["1718533"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We show that variants of spectral sparsification routines can preserve the total spanning tree counts of graphs. By Kirchhoff's matrix-tree theorem, this is equivalent to preserving the determinant of a graph Laplacian minor or, equivalently, of any symmetric diagonally dominant matrix (SDDM). Our analyses utilize this combinatorial connection to bridge the gap between statistical leverage scores\/effective resistances and the analysis of random graphs by Janson [ Combin. Probab. Comput., 3 (1994), pp. 97--126]. This leads to a routine that, in quadratic time, sparsifies a graph down to about $n^{1.5}$ edges in a way that preserves both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Choleksy factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a $(1 \\pm \\delta)$ approximation to the determinant of any SDDM matrix with constant probability in about $n^2 \\delta^{-2}$ time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates, in about $n^2 \\delta^{-2}$ time, a spanning tree of a weighted undirected graph from a distribution with a total variation distance of $\\delta$ from the $\\boldsymbol{\\mathit{w}}$-uniform distribution.<\/jats:p>","DOI":"10.1137\/18m1165979","type":"journal-article","created":{"date-parts":[[2020,3,10]],"date-time":"2020-03-10T09:32:06Z","timestamp":1583832726000},"page":"FOCS17-350-FOCS17-408","source":"Crossref","is-referenced-by-count":3,"title":["Determinant-Preserving Sparsification of SDDM Matrices"],"prefix":"10.1137","volume":"49","author":[{"given":"David","family":"Durfee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Peebles","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anup B.","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,3,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/0403039"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"A. Asadpour, M. X. Goemans, A. Madry, S. O. Gharan, and A. Saberi (2010),\n                      An $O({log} \\ n\/{log} \\ {log} \\ n)$-approximation algorithm for the asymmetric traveling salesman problem\n                      , in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10), SIAM, Philadelphia, pp. 379-389,https:\/\/doi.org\/10.1137\/1.9781611973075.32.","DOI":"10.1137\/1.9781611973075.32"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. A. Bencz\u00far and D. R. Karger (1996),\n                      Approximating s-t minimum cuts in O\u0342$(n2)$ time\n                      , in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC '96), ACM, New York, pp. 47-55.","DOI":"10.1145\/237814.237827"},{"key":"atypb6","unstructured":"C. Boutsidis, P. Drineas, P. Kambadur, and A. Zouzias (2015),\n                      A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix\n                      , preprint,https:\/\/arxiv.org\/abs\/1503.00374v1."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"A. Broder (1989),\n                      Generating random spanning trees\n                      , in Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), IEEE, Piscataway, NJ, pp. 442-447.","DOI":"10.1109\/SFCS.1989.63516"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989121"},{"key":"atypb9","first-page":"364","volume":"40","author":"Cheng D.","year":"2015","journal-title":"Mach. Learn. Res."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"M. B. Cohen (2016),\n                      Nearly tight oblivious subspace embeddings by trace inequalities\n                      , in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, pp. 278-287,https:\/\/doi.org\/10.1137\/1.9781611974331.ch21.","DOI":"10.1137\/1.9781611974331.ch21"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. B. Cohen, J. A. Kelner, J. Peebles, R. Peng, A. Rao, A. Sidford, and A. Vladu (2017),\n                      Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), ACM, New York, pp. 410-419.","DOI":"10.1145\/3055399.3055463"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"M. B. Cohen and R. Peng (2015),\n                      $\\ell_p$ row sampling by Lewis weights\n                      , in Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC '15), ACM, New York, pp. 183-192.","DOI":"10.1145\/2746539.2746567"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90016-3"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0014"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"D. Durfee, R. Kyng, J. Peebles, A. B. Rao, and S. Sachdeva (2016),\n                      Sampling random spanning trees faster than matrix multiplication\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), ACM, New York, pp. 730-742.","DOI":"10.1145\/3055399.3055499"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"atypb17","unstructured":"R. M. Foster (1948),\n                      The average impedance of an electrical network\n                      , in Reissner Anniversary Volume, Contributions to Applied Mechanics, J. W. Edwards, Ann Arbor, MI, pp. 333-340."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"W. S. Fung, R. Hariharan, N. J. Harvey, and D. Panigrahi (2011),\n                      A general framework for graph sparsification\n                      , in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, pp. 71-80.","DOI":"10.1145\/1993636.1993647"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"N. Goyal, L. Rademacher, and S. Vempala (2009),\n                      Expanders via random spanning trees\n                      , in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), SIAM, Philadelphia, pp. 576-585,https:\/\/doi.org\/10.1137\/1.9781611973068.64.","DOI":"10.1137\/1.9781611973068.64"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90022-6"},{"key":"atypb21","unstructured":"I. Han, D. Malioutov, and J. Shin (2015),\n                      Large-scale log-determinant computation through stochastic Chebyshev expansions\n                      , in Proceedings of the 32nd International Conference on Machine Learning, Lille, France, pp. 908-917."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"N. J. A. Harvey and K. Xu (2016),\n                      Generating random spanning trees via fast matrix multiplication\n                      , in LATIN 2016: Theoretical Informatics, Lecture Notes in Comput. Sci. 9644, Springer, Berlin, pp. 522-535.","DOI":"10.1007\/978-3-662-49529-2_39"},{"key":"atypb23","unstructured":"T. Hunter, A. El Alaoui, and A. M. Bayen (2014),\n                      Computing the Log-Determinant of Symmetric, Diagonally Dominant Matrices in Near-Linear Time\n                      , preprint,http:\/\/arxiv.org\/abs\/1408.1693."},{"key":"atypb24","unstructured":"I. C. F. Ipsen and D. J. Lee (2011),\n                      Determinant Approximations\n                      , preprint,https:\/\/arxiv.org\/abs\/1105.0437."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001012"},{"key":"atypb26","unstructured":"G. Jindal, P. Kolev, R. Peng, and S. Sawlani (2017),\n                      Density Independent Algorithms for Sparsifying k-step Random Walks\n                      , preprint,https:\/\/arxiv.org\/abs\/1702.06110."},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"J. Kelner and A. Madry (2009),\n                      Faster generation of random spanning trees\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), IEEE, Piscataway, NJ, pp. 13-21.","DOI":"10.1109\/FOCS.2009.75"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/andp.18471481202"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90002-V"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"R. Kyng, Y. T. Lee, R. Peng, S. Sachdeva, and D. A. Spielman (2016),\n                      Sparsified Cholesky and multigrid solvers for connection Laplacians\n                      , in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), ACM, New York, pp. 842-850.","DOI":"10.1145\/2897518.2897640"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"R. Lyons and Y. Peres (2016),\n                      Probability on Trees and Networks\n                      , Cambridge Ser. Statist. Probab. Math. 42, Cambridge University Press, New York.","DOI":"10.1017\/9781316672815"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"A. Madry, D. Straszak, and J. Tarnawski (2015),\n                      Fast generation of random spanning trees and the effective resistance metric\n                      , in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 2019-2036,https:\/\/doi.org\/10.1137\/1.9781611973730.134.","DOI":"10.1137\/1.9781611973730.134"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"R. Peng and D. A. Spielman (2014),\n                      An efficient parallel solver for SDD linear systems\n                      , in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14), ACM, New York, pp. 333-342.","DOI":"10.1145\/2591796.2591832"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"A. Schild (2018),\n                      An almost-linear time algorithm for uniform random spanning tree generation\n                      , in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), ACM, New York, pp. 214-227.","DOI":"10.1145\/3188745.3188852"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1561\/0400000054"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"R. Walker (1992),\n                      Book review of S. Skiena, \u201cImplementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica,\u201d Addison-Wesley,\n                      1990, Math. Gaz., 76, pp. 286-288.","DOI":"10.2307\/3619148"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"V. V. Williams (2012),\n                      Multiplying matrices faster than Coppersmith-Winograd\n                      , in Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12), ACM, New York, pp. 887-898,https:\/\/doi.org\/10.1145\/2213977.2214056.","DOI":"10.1145\/2213977.2214056"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1165979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:46Z","timestamp":1787336746000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1165979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1165979"],"URL":"https:\/\/doi.org\/10.1137\/18m1165979","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}