{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T18:45:08Z","timestamp":1754160308700,"version":"3.41.2"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"NSF CAREER Award","award":["CCF-1844855"],"award-info":[{"award-number":["CCF-1844855"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,7,31]]},"abstract":"<jats:p>\n            In this article, we provide an\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            loglog\n            <jats:sup>\n              <jats:italic toggle=\"yes\">O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            log (1\/\u03b5))-expected time algorithm for solving Laplacian systems on\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            -node\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            -edge graphs, improving upon the previous best expected runtime of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(m \\sqrt {\\log n} \\mathrm{log log}^{O(1)} n \\log (1\/\\epsilon))\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            achieved by Cohen et\u00a0al. [\n            <jats:xref ref-type=\"bibr\">12<\/jats:xref>\n            ]. To obtain this result, we provide efficient constructions of low spectral stretch graph approximations with improved stretch and sparsity bounds. As motivation for this work, we show that, for every set of vectors in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {R}^d\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            (not just those induced by graphs) and all integer\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            &gt; 1, there exist an ultra-sparsifier with\n            <jats:italic toggle=\"yes\">d<\/jats:italic>\n            -1 +\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">d\/k<\/jats:italic>\n            ) re-weighted vectors of relative condition number at most\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            . For small\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            , this improves upon the previous best known multiplicative factor of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k \\cdot \\tilde{O}(\\log d)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , which is only known for the graph case. Additionally, in the graph case, we employ our low-stretch subgraph construction to obtain\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            - 1 +\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">n\/k<\/jats:italic>\n            )-edge ultrasparsifiers of relative condition number\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            <jats:sup>1+o(1)<\/jats:sup>\n            for\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            = \u03c9 (log\n            <jats:sup>\u03b4<\/jats:sup>\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            ) for any \u03b4 &gt; 0: this improves upon the previous work for\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            =\n            <jats:italic toggle=\"yes\">o<\/jats:italic>\n            (exp (log\n            <jats:sup>1\/2-\u03b4<\/jats:sup>\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            )).\n          <\/jats:p>","DOI":"10.1145\/3593809","type":"journal-article","created":{"date-parts":[[2024,2,3]],"date-time":"2024-02-03T00:01:09Z","timestamp":1706918469000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-9964-893X","authenticated-orcid":false,"given":"Arun","family":"Jambulapati","sequence":"first","affiliation":[{"name":"University of Washington","place":["USA"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2675-7610","authenticated-orcid":false,"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University","place":["USA"]}]}],"member":"320","published-online":{"date-parts":[[2025,7,26]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_3_4_4_2","first-page":"161","volume-title":"Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, (Dallas, TX, May 23-26, 1998)","author":"Bartal Yair","year":"1998","unstructured":"Yair Bartal. 1998. On approximating arbitrary metrices by tree metrics. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, (Dallas, TX, May 23-26, 1998), Jeffrey Scott Vitter (Ed.). ACM, 161\u2013168. 10.1145\/276698.276725"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/130949117"},{"key":"e_1_3_4_6_2","article-title":"Fully-dynamic graph sparsifiers against an adaptive adversary","volume":"2004","author":"Bernstein Aaron","year":"2020","unstructured":"Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. 2020. Fully-dynamic graph sparsifiers against an adaptive adversary. CoRR abs\/2004.08432 (2020). arxiv:2004.08432https:\/\/arxiv.org\/abs\/2004.08432.","journal-title":"CoRR"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9444-5"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331588"},{"key":"e_1_3_4_9_2","first-page":"13900","volume-title":"Advances in Neural Information Processing Systems 32nd Annual Conference on Neural Information Processing Systems 2019 (NeurIPS 2019), (8-14 December 2019, Vancouver, BC, Canada)","author":"Bubeck S\u00e9bastien","year":"2019","unstructured":"S\u00e9bastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. 2019. Complexity of highly parallel non-smooth convex optimization. In Advances in Neural Information Processing Systems 32nd Annual Conference on Neural Information Processing Systems 2019 (NeurIPS 2019), (8-14 December 2019, Vancouver, BC, Canada). 13900\u201313909."},{"key":"e_1_3_4_10_2","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1145\/3055399.3055463","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017) (Montreal, QC, Canada, June 19-23, 2017)","author":"Cohen Michael B.","year":"2017","unstructured":"Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. 2017. Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017) (Montreal, QC, Canada, June 19-23, 2017), Hamed Hatami, Pierre McKenzie, and Valerie King (Eds.). ACM, 410\u2013419. 10.1145\/3055399.3055463"},{"key":"e_1_3_4_11_2","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1109\/FOCS.2016.69","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), (9-11 October 2016, Hyatt Regency, New Brunswick, NJ)","author":"Cohen Michael B.","year":"2016","unstructured":"Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. 2016. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), (9-11 October 2016, Hyatt Regency, New Brunswick, NJ), Irit Dinur (Ed.). IEEE Computer Society, 583\u2013592. 10.1109\/FOCS.2016.69"},{"key":"e_1_3_4_12_2","first-page":"343","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC 2014), (New York, NY, May 31 - June 03, 2014)","author":"Cohen Michael B.","year":"2014","unstructured":"Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. 2014. Solving SDD linear systems in nearly mlog \\({}^{\\mbox{1\/2}}\\) n time. In Proceedings of the Symposium on Theory of Computing (STOC 2014), (New York, NY, May 31 - June 03, 2014). 343\u2013352."},{"key":"e_1_3_4_13_2","article-title":"Preconditioning in expectation","volume":"1401","author":"Cohen Michael B.","year":"2014","unstructured":"Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki, Richard Peng, and Anup B. Rao. 2014. Preconditioning in expectation. CoRR abs\/1401.6236 (2014). arxiv:1401.6236http:\/\/arxiv.org\/abs\/1401.6236.","journal-title":"CoRR"},{"key":"e_1_3_4_14_2","article-title":"Uniform sampling for matrix approximation","volume":"1408","author":"Cohen Michael B.","year":"2014","unstructured":"Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. 2014. Uniform sampling for matrix approximation. CoRR abs\/1408.5099 (2014).","journal-title":"CoRR"},{"key":"e_1_3_4_15_2","first-page":"451","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing, (Victoria, British Columbia, Canada, May 17-20, 2008)","author":"Daitch Samuel I.","year":"2008","unstructured":"Samuel I. Daitch and Daniel A. Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, (Victoria, British Columbia, Canada, May 17-20, 2008), Cynthia Dwork (Ed.). ACM, 451\u2013460."},{"issue":"1","key":"e_1_3_4_16_2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s10107-013-0677-5","article-title":"First-order methods of smooth convex optimization with inexact oracle","volume":"146","author":"Devolder Olivier","year":"2014","unstructured":"Olivier Devolder, Fran\u00e7ois Glineur, and Yurii E. Nesterov. 2014. First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146, 1-2 (2014), 37\u201375.","journal-title":"Math. Program."},{"key":"e_1_3_4_17_2","first-page":"169","volume-title":"Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC 2011), (San Jose, CA, June 6-8, 2011)","author":"Dinitz Michael","year":"2011","unstructured":"Michael Dinitz and Robert Krauthgamer. 2011. Fault-tolerant spanners: Better and simpler. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC 2011), (San Jose, CA, June 6-8, 2011), Cyril Gavoille and Pierre Fraigniaud (Eds.). ACM, 169\u2013178. 10.1145\/1993806.1993830"},{"key":"e_1_3_4_18_2","first-page":"143","volume-title":"Proceedings of the 15th International Conference on Principles of Distributed Systems-(OPODIS 2011), (Toulouse, France, December 13-16, 2011). (Lecture Notes in Computer Science)","volume":"7109","author":"Gavoille Cyril","year":"2011","unstructured":"Cyril Gavoille, Quentin Godfroy, and Laurent Viennot. 2011. Node-disjoint multipath spanners and their relationship with fault-tolerant spanners. In Proceedings of the 15th International Conference on Principles of Distributed Systems-(OPODIS 2011), (Toulouse, France, December 13-16, 2011). (Lecture Notes in Computer Science), Antonio Fern\u00e1ndez Anta, Giuseppe Lipari, and Matthieu Roy (Eds.), Vol. 7109. Springer, 143\u2013158. 10.1007\/978-3-642-25873-2_11"},{"key":"e_1_3_4_19_2","first-page":"1894","volume-title":"Proceedings of the Conference on Learning Theory (COLT 2020), (9-12 July 2020, Virtual Event [Graz, Austria])","author":"Hinder Oliver","year":"2020","unstructured":"Oliver Hinder, Aaron Sidford, and Nimit Sharad Sohoni. 2020. Near-optimal methods for minimizing star-convex functions and beyond. In Proceedings of the Conference on Learning Theory (COLT 2020), (9-12 July 2020, Virtual Event [Graz, Austria]). 1894\u20131938."},{"key":"e_1_3_4_20_2","first-page":"217","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), (Portland, OR, January 5-7, 2014)","author":"Kelner Jonathan A.","year":"2014","unstructured":"Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2014. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), (Portland, OR, January 5-7, 2014). 217\u2013226."},{"key":"e_1_3_4_21_2","first-page":"911","volume-title":"Proceedings of the Symposium on Theory of Computing Conference (STOC\u201913), (Palo Alto, CA, June 1-4, 2013","author":"Kelner Jonathan A.","year":"2013","unstructured":"Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. 2013. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In Proceedings of the Symposium on Theory of Computing Conference (STOC\u201913), (Palo Alto, CA, June 1-4, 2013), Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (Eds.). ACM, 911\u2013920. 10.1145\/2488608.2488724"},{"key":"e_1_3_4_22_2","first-page":"86","volume-title":"Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS\u201996) (Burlington, VT, 14-16 October, 1996)","author":"Kleinberg Jon M.","year":"1996","unstructured":"Jon M. Kleinberg and Ronitt Rubinfeld. 1996. Short paths in expander graphs. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS\u201996) (Burlington, VT, 14-16 October, 1996). IEEE Computer Society, 86\u201395."},{"key":"e_1_3_4_23_2","first-page":"57","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, (STOC 2010), (Cambridge, MA, 5-8 June 2010)","author":"Kolla Alexandra","year":"2010","unstructured":"Alexandra Kolla, Yury Makarychev, Amin Saberi, and Shang-Hua Teng. 2010. Subgraph sparsification and nearly optimal ultrasparsifiers. In Proceedings of the 42nd ACM Symposium on Theory of Computing, (STOC 2010), (Cambridge, MA, 5-8 June 2010), Leonard J. Schulman (Ed.). ACM, 57\u201366. 10.1145\/1806689.1806699"},{"key":"e_1_3_4_24_2","first-page":"266","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), (February 29th - March 3rd, 2012, Paris, France) (LIPIcs)","volume":"14","author":"Koutis Ioannis","year":"2012","unstructured":"Ioannis Koutis, Alex Levin, and Richard Peng. 2012. Improved spectral sparsification and numerical algorithms for SDD matrices. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), (February 29th - March 3rd, 2012, Paris, France) (LIPIcs), Christoph D\u00fcrr and Thomas Wilke (Eds.), Vol. 14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 266\u2013277."},{"key":"e_1_3_4_25_2","first-page":"590","volume-title":"Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, (FOCS 2011) (Palm Springs, CA, October 22-25, 2011)","author":"Koutis Ioannis","year":"2011","unstructured":"Ioannis Koutis, Gary L. Miller, and Richard Peng. 2011. A nearly-m log n time solver for SDD linear systems. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, (FOCS 2011) (Palm Springs, CA, October 22-25, 2011), Rafail Ostrovsky (Ed.). IEEE Computer Society, 590\u2013598. 10.1109\/FOCS.2011.85"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"e_1_3_4_27_2","first-page":"842","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), (Cambridge, MA, June 18-21, 2016)","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. 2016. Sparsified Cholesky and multigrid solvers for connection Laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), (Cambridge, MA, June 18-21, 2016). 842\u2013850."},{"key":"e_1_3_4_28_2","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1109\/FOCS.2016.68","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), (9-11 October 2016, Hyatt Regency, New Brunswick, NJ)","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian elimination for Laplacians\u2014fast, sparse, and simple. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), (9-11 October 2016, Hyatt Regency, New Brunswick, NJ), Irit Dinur (Ed.). IEEE Computer Society, 573\u2013582. 10.1109\/FOCS.2016.68"},{"key":"e_1_3_4_29_2","article-title":"Probabilistic spectral sparsification in sublinear time","volume":"1401","author":"Lee Yin Tat","year":"2014","unstructured":"Yin Tat Lee. 2014. Probabilistic spectral sparsification in sublinear time. CoRR abs\/1401.0085 (2014). arxiv:1401.0085http:\/\/arxiv.org\/abs\/1401.0085.","journal-title":"CoRR"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","unstructured":"Yin Tat Lee and Aaron Sidford. 2013. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201913) (26-29 October 2013 Berkeley CA). IEEE Computer Society 147\u2013156. 10.1109\/FOCS.2013.24","DOI":"10.1109\/FOCS.2013.24"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384268"},{"key":"e_1_3_4_32_2","first-page":"2602","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), (San Diego, CA January 6-9, 2019)","author":"Liu Yang P.","year":"2019","unstructured":"Yang P. Liu, Sushant Sachdeva, and Zejun Yu. 2019. Short cycles via low-diameter decompositions. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), (San Diego, CA January 6-9, 2019), Timothy M. Chan (Ed.). SIAM, 2602\u20132615. 10.1137\/1.9781611975482.161"},{"key":"e_1_3_4_33_2","first-page":"196","volume-title":"Proeedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201913), (Montreal, QC, Canada - July 23-25, 2013)","author":"Miller Gary L.","year":"2013","unstructured":"Gary L. Miller, Richard Peng, and Shen Chen Xu. 2013. Parallel graph decompositions using random shifts. In Proeedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201913), (Montreal, QC, Canada - July 23-25, 2013). 196\u2013203."},{"issue":"2","key":"e_1_3_4_34_2","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1137\/110833786","article-title":"An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods","volume":"23","author":"Monteiro Renato D. C.","year":"2013","unstructured":"Renato D. C. Monteiro and Benar Fux Svaiter. 2013. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM J. Optim. 23, 2 (2013), 1092\u20131125.","journal-title":"SIAM J. Optim."},{"key":"e_1_3_4_35_2","first-page":"543","article-title":"A method for solving the convex programming problem with convergence rate  \\(O(1\/k^2)\\)","volume":"269","author":"Nesterov Y.","year":"1983","unstructured":"Y. Nesterov. 1983. A method for solving the convex programming problem with convergence rate \\(O(1\/k^2)\\) . Proceedings of the USSR Academy of Sciences 269 (1983), 543\u2013547.","journal-title":"Proceedings of the USSR Academy of Sciences"},{"key":"e_1_3_4_36_2","author":"Peng Richard","year":"2013","unstructured":"Richard Peng. 2013. Algorithm Design using Spectral Graph Theory. Ph.D dissertation (2013). http:\/\/reports-archive.adm.cs.cmu.edu\/anon\/2013\/CMU-CS-13-121.pdf.","journal-title":"Ph.D dissertation"},{"key":"e_1_3_4_37_2","first-page":"1862","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), (Arlington, VA, January 10-12, 2016)","author":"Peng Richard","year":"2016","unstructured":"Richard Peng. 2016. Approximate undirected maximum flows in \\({\\it O}({\\it m}polylog({\\it n}))\\) Time. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), (Arlington, VA, January 10-12, 2016). 1862\u20131867."},{"key":"e_1_3_4_38_2","first-page":"333","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC 2014), (New York, NY, May 31 - June 03, 2014)","author":"Peng Richard","year":"2014","unstructured":"Richard Peng and Daniel A. Spielman. 2014. An efficient parallel solver for SDD linear systems. In Proceedings of the Symposium on Theory of Computing (STOC 2014), (New York, NY, May 31 - June 03, 2014), David B. Shmoys (Ed.). ACM, 333\u2013342. 10.1145\/2591796.2591832"},{"key":"e_1_3_4_39_2","first-page":"2616","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), (San Diego, CA, January 6-9, 2019)","author":"Saranurak Thatchaphol","year":"2019","unstructured":"Thatchaphol Saranurak and Di Wang. 2019. Expander decomposition and pruning: Faster, stronger, and simpler. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), (San Diego, CA, January 6-9, 2019), Timothy M. Chan (Ed.). SIAM, 2616\u20132635. 10.1137\/1.9781611975482.162"},{"key":"e_1_3_4_40_2","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Number v. 1 in Algorithms and Combinatorics. Springer.2002036693https:\/\/books.google.com\/books?id=mqGeSQ6dJycC."},{"key":"e_1_3_4_41_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1109\/FOCS.2013.36","volume-title":"Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013) (26-29 October, 2013, Berkeley, CA)","author":"Sherman Jonah","year":"2013","unstructured":"Jonah Sherman. 2013. Nearly maximum flows in nearly linear time. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013) (26-29 October, 2013, Berkeley, CA). 263\u2013269."},{"key":"e_1_3_4_42_2","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1145\/3055399.3055501","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017) (Montreal, QC, Canada, June 19-23, 2017)","author":"Sherman Jonah","year":"2017","unstructured":"Jonah Sherman. 2017. Area-convexity, l \\({}_{\\infty}\\) regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017) (Montreal, QC, Canada, June 19-23, 2017), Hamed Hatami, Pierre McKenzie, and Valerie King (Eds.). ACM, 452\u2013460."},{"key":"e_1_3_4_43_2","first-page":"563","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing(Victoria, British Columbia, Canada, May 17-20, 2008)","author":"Spielman Daniel A.","year":"2008","unstructured":"Daniel A. Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing(Victoria, British Columbia, Canada, May 17-20, 2008), Cynthia Dwork (Ed.). ACM, 563\u2013568. 10.1145\/1374376.1374456"},{"key":"e_1_3_4_44_2","first-page":"81","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing(Chicago, IL, June 13-16, 2004)","author":"Spielman Daniel A.","year":"2004","unstructured":"Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing(Chicago, IL, June 13-16, 2004), L\u00e1szl\u00f3 Babai (Ed.). ACM, 81\u201390."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3593809","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T09:28:25Z","timestamp":1753522105000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593809"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,26]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7,31]]}},"alternative-id":["10.1145\/3593809"],"URL":"https:\/\/doi.org\/10.1145\/3593809","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,7,26]]},"assertion":[{"value":"2021-05-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}