{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:22:40Z","timestamp":1787322160967,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2123224"],"award-info":[{"award-number":["DMS-2123224"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1929284"],"award-info":[{"award-number":["DMS-1929284"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007812","name":"University of Washington","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007812","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We propose an approach to graph sparsification based on the idea of preserving the smallest [Formula: see text] eigenvalues and eigenvectors of the graph Laplacian. This is motivated by the fact that small eigenvalues and their associated eigenvectors tend to be more informative of the global structure and geometry of the graph than larger eigenvalues and their eigenvectors. The set of all weighted subgraphs of a graph [Formula: see text] that have the same first [Formula: see text] eigenvalues (and eigenvectors) as [Formula: see text] is the intersection of a polyhedron with a cone of positive semidefinite matrices. We discuss the geometry of these sets and deduce the natural scale of [Formula: see text]. Various families of graphs illustrate our construction.<\/jats:p>","DOI":"10.1137\/23m1610069","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T04:01:13Z","timestamp":1739851273000},"page":"449-483","source":"Crossref","is-referenced-by-count":1,"title":["Spectrahedral Geometry of Graph Sparsifiers"],"prefix":"10.1137","volume":"39","author":[{"given":"Catherine","family":"Babecki","sequence":"first","affiliation":[{"name":"Departments of Mathematics and Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7745-4217","authenticated-orcid":true,"given":"Stefan","family":"Steinerberger","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Washington, Seattle, WA 98195-4350 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2189-2303","authenticated-orcid":true,"given":"Rekha R.","family":"Thomas","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Washington, Seattle, WA 98195-4350 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-021-09852-z"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/22M1528768"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01861-0"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"J. Batson, D. Spielman, and N. Srivastava, Twice-Ramanujan sparsifiers, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM, New York, 2009, pp. 255\u2013262.","DOI":"10.1145\/1536414.1536451"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1162\/089976603321780317"},{"key":"ref7","unstructured":"R. Bhattacharjee, G. Dexter, C. Musco, A. Ray, and D. P. Woodruff, Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra, preprint, arXiv:2305.05826, 2024."},{"key":"ref8","series-title":"MOS-SIAM Series on Optimization 13","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"Blekherman G.","year":"2013"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1939-6"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, in Proceedings of the Princeton Conference in Honor of Prof. S. Bochner, Princeton University Press, Princeton, NJ, 1969, pp. 195\u2013199.","DOI":"10.1515\/9781400869312-013"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnt.2017.09.021"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2018.04.001"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2006.04.006"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/2746241"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.3934\/fods.2021015"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2018.09.001"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2020.07.012"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079816"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"J. Lee, S. Oveis Gharan, and L. Trevisan, Multi-way spectral partitioning and higher-order Cheeger inequalities, in STOC\u201912\u2014Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 1117\u20131130.","DOI":"10.1145\/2213977.2214078"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.09.023"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(97)10080-5"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"D. Spielman and S.H. Teng, 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, ACM, New York, 2004.","DOI":"10.1145\/1007352.1007372"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22485"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnz176"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.113246"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1610069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:48Z","timestamp":1787318328000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1610069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,18]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1137\/23M1610069"],"URL":"https:\/\/doi.org\/10.1137\/23m1610069","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,18]]}}}