{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:27Z","timestamp":1781078307573,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":91,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["340506"],"award-info":[{"award-number":["340506"]}]},{"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"}]},{"name":"Marshall Plan Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316379","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"914-925","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Fully dynamic spectral vertex sparsifiers and applications"],"prefix":"10.1145","author":[{"given":"David","family":"Durfee","sequence":"first","affiliation":[{"name":"Georgia Tech, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Gao","sequence":"additional","affiliation":[{"name":"Georgia Tech, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gramoz","family":"Goranci","sequence":"additional","affiliation":[{"name":"University of Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Georgia Tech, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Ittai Abraham Shiri Chechik and Sebastian Krinninger. 2017.  Ittai Abraham Shiri Chechik and Sebastian Krinninger. 2017."},{"key":"e_1_3_2_1_2_1","volume-title":"Symposium on Discrete Algorithms (SODA). 440\u2013452","author":"Fully"},{"key":"e_1_3_2_1_3_1","volume-title":"On Fully Dynamic Graph Sparsifiers. In Symposium on Foundations of Computer Science (FOCS). 335\u2013344","author":"Abraham Ittai","year":"2016"},{"key":"e_1_3_2_1_4_1","unstructured":"Alexandr Andoni Anupam Gupta and Robert Krauthgamer. 2014.  Alexandr Andoni Anupam Gupta and Robert Krauthgamer. 2014."},{"key":"e_1_3_2_1_5_1","volume-title":"Symposium on Discrete algorithms (SODA). 279\u2013293","author":"Towards"},{"key":"e_1_3_2_1_6_1","unstructured":"Alexandr Andoni Robert Krauthgamer and Yosef Pogrow. 2019.  Alexandr Andoni Robert Krauthgamer and Yosef Pogrow. 2019."},{"key":"e_1_3_2_1_7_1","volume-title":"Solving Linear Systems in Sublinear Time. In Innovations in Theoretical Computer Science Conference (ITCS). 3:1\u20133:19","author":"On"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194264988"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914140"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"e_1_3_2_1_11_1","unstructured":"Joshua Batson Daniel A. Spielman Nikhil Srivastava and Shang-Hua Teng. 2013.  Joshua Batson Daniel A. Spielman Nikhil Srivastava and Shang-Hua Teng. 2013."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_3_2_1_14_1","unstructured":"Aaron Bernstein and Shiri Chechik. 2016.  Aaron Bernstein and Shiri Chechik. 2016."},{"key":"e_1_3_2_1_15_1","volume-title":"Symposium on Theory of Computing (STOC). 389\u2013397","author":"Deterministic"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.32"},{"key":"e_1_3_2_1_18_1","unstructured":"Dehua Cheng Yu Cheng Yan Liu Richard Peng and Shang-Hua Teng. 2015.  Dehua Cheng Yu Cheng Yan Liu Richard Peng and Shang-Hua Teng. 2015."},{"key":"e_1_3_2_1_19_1","volume-title":"Spectral Sparsification. Conference on Learning Theory (COLT)","author":"Gaussian Graphical Efficient Sampling","year":"2015"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_3_2_1_21_1","unstructured":"Florian D\u00f6rfler and Francesco Bullo. 2013.  Florian D\u00f6rfler and Francesco Bullo. 2013."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Kron Reduction of Graphs With Applications to Electrical Networks. IEEE Trans. on Circuits and Systems 60-I 1 (2013) 150\u2013163.  Kron Reduction of Graphs With Applications to Electrical Networks. IEEE Trans. on Circuits and Systems 60-I 1 (2013) 150\u2013163.","DOI":"10.1109\/TCSI.2012.2215780"},{"key":"e_1_3_2_1_23_1","unstructured":"David Durfee Rasmus Kyng John Peebles Anup B Rao and Sushant Sachdeva. 2017.  David Durfee Rasmus Kyng John Peebles Anup B Rao and Sushant Sachdeva. 2017."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055499"},{"key":"e_1_3_2_1_25_1","volume-title":"Symposium on Foundations of Computer Science (FOCS). 926\u2013937","author":"Durfee David"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028278"},{"key":"e_1_3_2_1_27_1","unstructured":"David Eppstein Zvi Galil Giuseppe F Italiano and Amnon Nissenzweig. 1997.  David Eppstein Zvi Galil Giuseppe F Italiano and Amnon Nissenzweig. 1997."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_2_1_29_1","unstructured":"Jittat Fakcharoenphol Satish Rao and Kunal Talwar. 2004.  Jittat Fakcharoenphol Satish Rao and Kunal Talwar. 2004."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_32_1","volume-title":"The Power of Vertex Sparsifiers in Dynamic Graph Algorithms. In European Symposium on Algorithms (ESA). 45:1\u201345:14","author":"Goranci Gramoz","year":"2017"},{"key":"e_1_3_2_1_33_1","volume-title":"Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs. In European Symposium on Algorithms (ESA). 40:1\u201340:15","author":"Goranci Gramoz","year":"2018"},{"key":"e_1_3_2_1_34_1","volume-title":"Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time. In European Symposium on Algorithms (ESA). 46:1\u201346:17","author":"Goranci Gramoz","year":"2016"},{"key":"e_1_3_2_1_35_1","unstructured":"Gramoz Goranci and Sebastian Krinninger. 2018. Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions. CoRR abs\/1804.04928 (2018). Available at: http:\/\/arxiv.org\/abs\/1804.04928.  Gramoz Goranci and Sebastian Krinninger. 2018. Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions. CoRR abs\/1804.04928 (2018). Available at: http:\/\/arxiv.org\/abs\/1804.04928."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.24"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/140957299"},{"key":"e_1_3_2_1_39_1","unstructured":"Announced at FOCS\u201913.  Announced at FOCS\u201913."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0855"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_42_1","unstructured":"Jacob Holm Eva Rotenberg and Christian Wulff-Nilsen. 2015.  Jacob Holm Eva Rotenberg and Christian Wulff-Nilsen. 2015."},{"key":"e_1_3_2_1_43_1","volume-title":"Fully-Dynamic Minimum Spanning Forest. In European Symposium on Algorithms (ESA). 742\u2013753","author":"Faster"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634090"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_47_1","unstructured":"Robert Krauthgamer and Inbal Rika. 2013.  Robert Krauthgamer and Inbal Rika. 2013."},{"key":"e_1_3_2_1_48_1","volume-title":"Symposium on Discrete algorithms (SODA). 1789\u20131799","author":"Mimicking"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_3_2_1_51_1","volume-title":"European Symposium on Algorithms (ESA). 155\u2013 166","author":"Lacki Jakub","year":"2011"},{"key":"e_1_3_2_1_52_1","unstructured":"Huan Li and Zhongzhi Zhang. 2018.  Huan Li and Zhongzhi Zhang. 2018."},{"key":"e_1_3_2_1_53_1","volume-title":"Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms. In Symposium on Discrete Algorithms (SODA). 2377\u20132396","author":"Kirchhoff Index"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_3_2_1_55_1","unstructured":"Andreas Loukas. 2018. Graph reduction by local variation. CoRR abs\/1808.10650 (2018).  Andreas Loukas. 2018. Graph reduction by local variation. CoRR abs\/1808.10650 (2018)."},{"key":"e_1_3_2_1_56_1","unstructured":"Andreas Loukas and Pierre Vandergheynst. 2018.  Andreas Loukas and Pierre Vandergheynst. 2018."},{"key":"e_1_3_2_1_57_1","volume-title":"Approximating Large Graphs with Smaller Graphs. In ICML (JMLR Workshop and Conference Proceedings)","volume":"80","author":"Spectrally"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.30"},{"key":"e_1_3_2_1_59_1","volume-title":"Fast Generation of Random Spanning Trees and the Effective Resistance Metric. In Symposium on Discrete Algorithms (SODA). 2019\u20132036","author":"Madry Aleksander","year":"2015"},{"key":"e_1_3_2_1_60_1","volume-title":"Vertex Sparsifiers and Lipschitz Extendability. In Symposium on Foundations of Computer Science (FOCS). 255\u2013264","author":"Makarychev Konstantin","year":"2010"},{"key":"e_1_3_2_1_61_1","volume-title":"Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size. In Symposium on Foundations of Computer Science (FOCS). 3\u201312","author":"Moitra Ankur","year":"2009"},{"key":"e_1_3_2_1_62_1","unstructured":"Danupon Nanongkai and Thatchaphol Saranurak. 2017.  Danupon Nanongkai and Thatchaphol Saranurak. 2017."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_3_2_1_64_1","unstructured":"Danupon Nanongkai Thatchaphol Saranurak and Christian Wulff-Nilsen. 2017.  Danupon Nanongkai Thatchaphol Saranurak and Christian Wulff-Nilsen. 2017."},{"key":"e_1_3_2_1_65_1","volume-title":"Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In Symposium on Foundations of Computer Science (FOCS). 950\u2013961","author":"Dynamic"},{"key":"e_1_3_2_1_66_1","unstructured":"Ofer Neiman and Shay Solomon. 2016.  Ofer Neiman and Shay Solomon. 2016."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Simple Deterministic Algorithms for Fully Dynamic Maximal Matching. ACM Trans. Algorithms 12 1 (2016) 7:1\u20137:15. Announced at STOC\u201913.  Simple Deterministic Algorithms for Fully Dynamic Maximal Matching. ACM Trans. Algorithms 12 1 (2016) 7:1\u20137:15. Announced at STOC\u201913.","DOI":"10.1145\/2700206"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_3_2_1_70_1","unstructured":"Richard Peng Bryce Sandlund and Daniel Dominic Sleator. 2017.  Richard Peng Bryce Sandlund and Daniel Dominic Sleator. 2017."},{"key":"e_1_3_2_1_71_1","unstructured":"Offline Dynamic Higher Connectivity. CoRR abs\/1708.03812 (2017). Available at: http:\/\/arxiv.org\/abs\/1708.03812.  Offline Dynamic Higher Connectivity. CoRR abs\/1708.03812 (2017). Available at: http:\/\/arxiv.org\/abs\/1708.03812."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591832"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374415"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.25"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188852"},{"key":"e_1_3_2_1_76_1","volume-title":"Localization of Electrical Flows. In Symposium on Discrete Algorithms (SODA). 1577\u20131584","author":"Schild Aaron","year":"2018"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_3_2_1_78_1","unstructured":"Shay Solomon. 2016.  Shay Solomon. 2016."},{"key":"e_1_3_2_1_79_1","volume-title":"Foundations of Computer Science (FOCS). 325\u2013334. STOC \u201919, June 23\u201326","author":"Maximal Fully Dynamic","year":"2019"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_2_1_82_1","unstructured":"D. Spielman and S. Teng. 2014.  D. Spielman and S. Teng. 2014."},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"crossref","unstructured":"Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric Diagonally Dominant Linear Systems. SIAM J. Matrix Anal. Appl. 35 3 (2014) 835\u2013885.  Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric Diagonally Dominant Linear Systems. SIAM J. Matrix Anal. Appl. 35 3 (2014) 835\u2013885.","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_1_84_1","volume-title":"Proceedings of the International Congress of Mathematicians.","author":"Spielman Daniel A.","year":"2010"},{"key":"e_1_3_2_1_85_1","unstructured":"Shang-Hua Teng. 2010.  Shang-Hua Teng. 2010."},{"key":"e_1_3_2_1_86_1","unstructured":"The Laplacian Paradigm: Emerging Algorithms for Massive Graphs. In Theory and Applications of Models of Computation. 2\u201314.  The Laplacian Paradigm: Emerging Algorithms for Massive Graphs. In Theory and Applications of Models of Computation. 2\u201314."},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0045-2"},{"key":"e_1_3_2_1_88_1","unstructured":"Tal Wagner Sudipto Guha Shiva Prasad Kasiviswanathan and Nina Mishra. 2018.  Tal Wagner Sudipto Guha Shiva Prasad Kasiviswanathan and Nina Mishra. 2018."},{"key":"e_1_3_2_1_89_1","volume-title":"Temporal Label Propagation. In International Conference on Machine Learning (ICML). 5082\u20135091","author":"Data Semi-Supervised"},{"key":"e_1_3_2_1_90_1","unstructured":"Christian Wulff-Nilsen. 2017.  Christian Wulff-Nilsen. 2017."},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316379","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316379","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316379","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316379"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":91,"alternative-id":["10.1145\/3313276.3316379","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316379","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}