{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:09Z","timestamp":1750220529631,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-155375, CCF-200901, DGE-175281"],"award-info":[{"award-number":["CCF-155375, CCF-200901, DGE-175281"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451129","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"396-407","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Support of closed walks and second eigenvalue multiplicity of graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9649-7370","authenticated-orcid":false,"given":"Theo","family":"McKenzie","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Michael Reichstein","family":"Rasmussen","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Srivastava","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929394"},{"volume-title":"Rounding semidefinite programming hierarchies via global correlation. In 2011 ieee 52nd annual symposium on foundations of computer science. Pages 472\u2013481","author":"Barak Boaz","key":"e_1_3_2_1_3_1","unstructured":"Boaz Barak, Prasad Raghavendra, and David Steurer. 2011. Rounding semidefinite programming hierarchies via global correlation. In 2011 ieee 52nd annual symposium on foundations of computer science. Pages 472\u2013481."},{"volume-title":"Modern graph theory. 184","author":"Bollob\u00e1s B\u00e9la","key":"e_1_3_2_1_4_1","unstructured":"B\u00e9la Bollob\u00e1s. 2013. Modern graph theory. 184, Springer Science & Business Media."},{"key":"e_1_3_2_1_5_1","first-page":"1","article-title":"The Spectral Radius and the Maximum Degree of Irregular Graphs","volume":"14","author":"Sebastian M","year":"2007","unstructured":"Sebastian M Cioab\\u a. 2007. The Spectral Radius and the Maximum Degree of Irregular Graphs. The Electronic Journal of Combinatorics, 14, 1, 2007. Pages R38.","journal-title":"The Electronic Journal of Combinatorics"},{"key":"e_1_3_2_1_6_1","first-page":"6","article-title":"A lower bound for the spectral radius of graphs with fixed diameter","volume":"31","author":"Sebastian M","year":"2010","unstructured":"Sebastian M Cioab\\u a, Edwin R Van Dam, Jack H Koolen, and Jae-Ho Lee. 2010. A lower bound for the spectral radius of graphs with fixed diameter. European Journal of Combinatorics, 31, 6, 2010. Pages 1560\u20131566.","journal-title":"European Journal of Combinatorics"},{"key":"e_1_3_2_1_7_1","first-page":"2007","article-title":"Principal eigenvectors of irregular graphs","volume":"16","author":"David Gregory Sebastian","year":"2007","unstructured":"Sebastian Cioab\\u a and David Gregory. 2007. Principal eigenvectors of irregular graphs. The Electronic Journal of Linear Algebra, 16, 2007.","journal-title":"The Electronic Journal of Linear Algebra"},{"key":"e_1_3_2_1_8_1","volume-title":"A study of eigenspaces of graphs. Linear algebra and its applications, 182","author":"Rowlinson Peter","year":"1993","unstructured":"Drago\\v s Cvetkovi\u0107, Peter Rowlinson, and Slobodan Simi\u0107. 1993. A study of eigenspaces of graphs. Linear algebra and its applications, 182, 1993. Pages 45\u201366."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Peter G Doyle and J Laurie Snell. 1984. Random walks and electric networks. 22 American Mathematical Soc..","DOI":"10.5948\/UPO9781614440222"},{"volume-title":"Some geometric aspects of graphs and their eigenfunctions","author":"Friedman Joel","key":"e_1_3_2_1_10_1","unstructured":"Joel Friedman. 1991. Some geometric aspects of graphs and their eigenfunctions. Princeton University, Department of Computer Science."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"volume-title":"Algebraic combinatorics. 6","author":"Godsil Chris","key":"e_1_3_2_1_12_1","unstructured":"Chris Godsil. 1993. Algebraic combinatorics. 6, CRC Press."},{"key":"e_1_3_2_1_13_1","volume-title":"Equiangular lines with a fixed angle. arXiv preprint arXiv:1907.12466","author":"Jiang Zilin","year":"2019","unstructured":"Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao. 2019. Equiangular lines with a fixed angle. arXiv preprint arXiv:1907.12466, 2019."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210136"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003209"},{"key":"e_1_3_2_1_16_1","volume-title":"Spectral algorithms for unique games. computational complexity, 20, 2","author":"Kolla Alexandra","year":"2011","unstructured":"Alexandra Kolla. 2011. Spectral algorithms for unique games. computational complexity, 20, 2, 2011. Pages 177\u2013206."},{"key":"e_1_3_2_1_17_1","volume-title":"Eigenvalue multiplicity and","author":"Lee James R","year":"2008","unstructured":"James R Lee and Yury Makarychev. 2008. Eigenvalue multiplicity and volume growth. arXiv preprint arXiv:0806.1745, 2008."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2665063"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214079"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnx082"},{"key":"e_1_3_2_1_22_1","first-page":"2015","article-title":"Interlacing families I: Bipartite Ramanujan graphs of all degrees","volume":"182","author":"Marcus Adam W","year":"2015","unstructured":"Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. 2015. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Annals of Mathematics, 182, 2015. Pages 307\u2013325.","journal-title":"Annals of Mathematics"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(81)90150-6"},{"volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Gharan Shayan Oveis","key":"e_1_3_2_1_24_1","unstructured":"Shayan Oveis Gharan and Luca Trevisan. 2013. A new regularity lemma and faster approximation algorithms for low threshold rank graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer. Pages 303\u2013316."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/22.3.209"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.07.023"},{"volume-title":"Spectral radius of graphs","author":"Stevanovic Dragan","key":"e_1_3_2_1_27_1","unstructured":"Dragan Stevanovic. 2014. Spectral radius of graphs. Academic Press."},{"key":"e_1_3_2_1_28_1","volume-title":"Characterizing graphs of maximum principal ratio. arXiv preprint arXiv:1511.06378","author":"Tait Michael","year":"2015","unstructured":"Michael Tait and Josh Tobin. 2015. Characterizing graphs of maximum principal ratio. arXiv preprint arXiv:1511.06378, 2015."},{"key":"e_1_3_2_1_29_1","first-page":"1","article-title":"Decreasing the spectral radius of a graph by link removals","volume":"84","author":"Mieghem Piet Van","year":"2011","unstructured":"Piet Van Mieghem, Dragan Stevanovi\u0107, Fernando Kuipers, Cong Li, Ruud Van De Bovenkamp, Daijie Liu, and Huijuan Wang. 2011. Decreasing the spectral radius of a graph by link removals. Physical Review E, 84, 1, 2011. Pages 7233.","journal-title":"Physical Review E"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451129","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451129","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":29,"alternative-id":["10.1145\/3406325.3451129","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451129","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}