{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T09:22:19Z","timestamp":1789723339207,"version":"4.0.1"},"reference-count":69,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/501100007224","name":"Connaught Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","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"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1637523"],"award-info":[{"award-number":["1637523"]}],"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":[[2023,12]]},"abstract":"<jats:p>We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition, which is a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus a small number of extra edges. A simple observation shows that every graph $G$ on $n$ vertices with $m$ edges can be decomposed in $O(mn)$ time into cycles of length at most $2 \\log n,$ and at most $2n$ extra edges. We give an $(m^{1+o(1)})$-time algorithm for constructing a short cycle decomposition, with cycles of length $n^{o(1)},$ and $n^{1+o(1)}$ extra edges. Both the existential and algorithmic variants of this decomposition enable us to make the following progress on several open problems in randomized graph algorithms: (1) We present an algorithm that runs in time $m^{1+o(1)}\\varepsilon^{-1.5}$ and returns $(1\\pm\\varepsilon)$-approximations to effective resistances of all edges, improving over the previous best runtime of $\\widetilde{{O}}(\\min\\{m\\varepsilon^{-2}, n^{2} \\varepsilon^{-1}\\})$. This routine in turn gives an algorithm for approximating the determinant of a graph Laplacian up to a factor of $(1\\pm \\varepsilon)$ in $m^{1 + o(1)} + n^{\\nicefrac{15}{8}+o(1)}\\varepsilon^{-\\nicefrac{7}{4}}$ time. (2) We show the existence of graphical spectral sketches with about $n\\varepsilon^{-1}$ edges, and also give efficient algorithms to construct them. A graphical spectral sketch is a distribution over sparse graphs $H$ such that for a fixed vector ${\\mathit{x}}$, we have ${{x}}^{\\top} {L}_H {{x}} = (1\\pm\\varepsilon) {{x}}^{\\top} {L}_G {{x}}$ and ${{x}}^{\\top} {L}^{+}_H {{x}} = (1\\pm\\varepsilon) {{x}}^{\\top} {L}^{+}_G {{x}}$ with high probability, where ${L}$ is the graph Laplacian and ${L}^{+}$ is its pseudoinverse. This implies the existence of resistance sparsifiers with about $n \\varepsilon^{-1}$ edges that preserve the effective resistance between every pair of vertices up to $(1\\pm\\varepsilon)$. (3) By combining short cycle decompositions with known tools in graph sparsification, we show the existence of nearly linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of Eulerian directed graphs. The latter is critical to recent breakthroughs on faster algorithms for solving linear systems in directed Laplacians. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for constructing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvement in each of these algorithms.<\/jats:p>","DOI":"10.1137\/19m1247632","type":"journal-article","created":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T12:28:45Z","timestamp":1591705725000},"page":"FOCS18-85-FOCS18-157","source":"Crossref","is-referenced-by-count":9,"title":["Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions"],"prefix":"10.1137","volume":"52","author":[{"given":"Timothy","family":"Chu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Gao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saurabh","family":"Sawlani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Junxing","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,6,9]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/2746539.2746610","volume-title":"Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015","author":"Zhu Z. Allen","year":"2015"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840753"},{"key":"atypb4","volume-title":"Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs, preprint, https:\/\/arxiv.org\/abs\/1805.02974","author":"Assadi S.","year":"2018"},{"key":"atypb5","first-page":"503","volume-title":"Proceedings of the 31st Annual Symposium on Foundations of Computer Science, St","author":"Awerbuch B.","year":"1990"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"atypb7","first-page":"1125","volume-title":"Proceedings of the 2008 ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Baswana S.","year":"2008"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.104"},{"key":"atypb12","volume-title":"Optimal Lower Bounds for Sketching Graph Cuts, preprint, https:\/\/arxiv.org\/abs\/1712.10261","author":"Carlson C.","year":"2017"},{"key":"atypb13","first-page":"364","volume-title":"Proceedings of the 28th Conference on Learning Theory","author":"Cheng D.","year":"2015"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10534"},{"key":"atypb15","first-page":"273","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC '11)","author":"Christiano P.","year":"2011"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055463"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.69"},{"key":"atypb19","first-page":"738","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM","author":"Dinitz M.","year":"2015"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.40"},{"key":"atypb21","volume-title":"Fully Dynamic Effective Resistances, preprint, https:\/\/arxiv.org\/abs\/1804.04038","author":"Durfee D.","year":"2018"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055499"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.90"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00019"},{"key":"atypb26","first-page":"333","author":"Foster R. M.","year":"1948","journal-title":"J. W. Edwards"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71924-5_27"},{"key":"atypb28","first-page":"2487","volume-title":"Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Jambulapati A.","year":"2018"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090267"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.16"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.013"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612676"},{"key":"atypb33","first-page":"266","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), C. D\u00fcrr and T. Wilke, eds., LIPIcs. Leibniz Int. Proc. Inform. 14","author":"Koutis I.","year":"2012"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"atypb36","unstructured":"R. Kyng,\n                      Approximate Gaussian Elimination\n                      , Ph.D. thesis, Yale University, 2017,http:\/\/rasmuskyng.com\/rjkyng-dissertation.pdf."},{"key":"atypb37","first-page":"842","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2016","author":"Kyng R.","year":"1892"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.132"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.68"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.24"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055477"},{"key":"atypb42","volume-title":"Current Flow Group Closeness Centrality for Complex Networks, preprint, https:\/\/arxiv.org\/abs\/1802.02556","author":"Li H.","year":"2018"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.153"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.161"},{"key":"atypb45","first-page":"353","volume-title":"Combinatorics, Paul Erd\u00f6s Is Eighty","volume":"2","author":"Lov\u00e1sz L.","year":"1993"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.30"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.134"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741125"},{"key":"atypb50","first-page":"1","volume-title":"Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), LIPIcs. Leibniz Int. Proc. Inform. 94","author":"Musco C.","year":"2018"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"atypb52","first-page":"1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019","author":"Parter M.","year":"2019"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch130"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591832"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374415"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.17"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.162"},{"key":"atypb58","unstructured":"P. Sarkar,\n                      Tractable Algorithms for Proximity Search on Large Graphs\n                      , Ph.D. thesis, Carnegie Mellon University, 2010,http:\/\/www.cs.cmu.edu\/ psarkar\/thesis\/sarkar_thesis.pdf."},{"key":"atypb59","first-page":"335","volume-title":"Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, AUAI Press","author":"Sarkar P.","year":"2007"},{"key":"atypb60","volume-title":"An Almost-Linear Time Algorithm for Uniform Random Spanning Tree Generation, preprint, https:\/\/arxiv.org\/abs\/1711.06455","author":"Schild A.","year":"2017"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"atypb64","first-page":"1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Spielman D. A.","year":"2010"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1561\/0400000051"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13562-0_2"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1247632","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:15Z","timestamp":1787337435000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1247632"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,9]]},"references-count":69,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1137\/19M1247632"],"URL":"https:\/\/doi.org\/10.1137\/19m1247632","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,9]]}}}