{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T16:15:11Z","timestamp":1772122511880,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520009","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1144-1157","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Sublinear time spectral density estimation"],"prefix":"10.1145","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[{"name":"Johns Hopkins University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aditya","family":"Krishnan","sequence":"additional","affiliation":[{"name":"Johns Hopkins University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Musco","sequence":"additional","affiliation":[{"name":"New York University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2017.06.016"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944349"},{"key":"e_1_3_2_1_3_1","volume-title":"the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time. In","author":"Banks Jess","year":"2020","unstructured":"Jess Banks , Jorge Vargas , Archit Kulkarni , and Nikhil Srivastava . 2019. Pseudospectral Shattering , the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time. In 2020 . Jess Banks, Jorge Vargas, Archit Kulkarni, and Nikhil Srivastava. 2019. Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time. In 2020."},{"key":"e_1_3_2_1_4_1","volume-title":"The Gradient Complexity of Linear Regression. In","author":"Braverman Mark","year":"2020","unstructured":"Mark Braverman , Elad Hazan , Max Simchowitz , and Blake Woodworth . 2020. The Gradient Complexity of Linear Regression. In 2020 . 125, 627\u2013647. Mark Braverman, Elad Hazan, Max Simchowitz, and Blake Woodworth. 2020. The Gradient Complexity of Linear Regression. In 2020. 125, 627\u2013647."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Vladimir Braverman Aditya Krishnan and Christopher Musco. 2021. Linear and sublinear time spectral density estimation. arXiv preprint arXiv:2104.03461.  Vladimir Braverman Aditya Krishnan and Christopher Musco. 2021. Linear and sublinear time spectral density estimation. arXiv preprint arXiv:2104.03461.","DOI":"10.1145\/3519935.3520009"},{"key":"e_1_3_2_1_6_1","volume-title":"Analysis of stochastic Lanczos quadrature for spectrum approximation. In","author":"Chen Tyler","year":"2021","unstructured":"Tyler Chen , Thomas Trogdon , and Shashanka Ubaru . 2021. Analysis of stochastic Lanczos quadrature for spectrum approximation. In 2021 . Tyler Chen, Thomas Trogdon, and Shashanka Ubaru. 2021. Analysis of stochastic Lanczos quadrature for spectrum approximation. In 2021."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1955-0071856-0"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220119"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049670"},{"key":"e_1_3_2_1_10_1","unstructured":"Prathamesh Dharangutte and Christopher Musco. 2021. Dynamic Trace Estimation. Preprint.  Prathamesh Dharangutte and Christopher Musco. 2021. Dynamic Trace Estimation. Preprint."},{"key":"e_1_3_2_1_11_1","volume-title":"Austin R Benson, and David Bindel","author":"Dong Kun","year":"2019","unstructured":"Kun Dong , Austin R Benson, and David Bindel . 2019 . Network density of states. In 2019. 1152\u20131161. Kun Dong, Austin R Benson, and David Bindel. 2019. Network density of states. In 2019. 1152\u20131161."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442684"},{"key":"e_1_3_2_1_13_1","volume-title":"An Investigation into Neural Net Optimization via Hessian Eigenvalue Density. In","author":"Ghorbani Behrooz","year":"2019","unstructured":"Behrooz Ghorbani , Shankar Krishnan , and Ying Xiao . 2019. An Investigation into Neural Net Optimization via Hessian Eigenvalue Density. In 2019 . 97, 2232\u20132241. Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. 2019. An Investigation into Neural Net Optimization via Hessian Eigenvalue Density. In 2019. 97, 2232\u20132241."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.90"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610919008812866"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1912-1500930-2"},{"key":"e_1_3_2_1_17_1","volume-title":"The Theory of Approximation","author":"Jackson Dunham","unstructured":"Dunham Jackson . 1930. The Theory of Approximation (Colloquium Publications, Vol . 11). American Mathematical Society . Dunham Jackson. 1930. The Theory of Approximation (Colloquium Publications, Vol. 11). American Mathematical Society."},{"key":"e_1_3_2_1_18_1","first-page":"1058","article-title":"On a functional space and certain extremum problems","volume":"115","author":"Kantorovich Leonid Vital\u2019evich","year":"1957","unstructured":"Leonid Vital\u2019evich Kantorovich and Gennadii Shlemovich Rubinshtein . 1957 . On a functional space and certain extremum problems . In Doklady Akademii Nauk. 115 , 1058 \u2013 1061 . Leonid Vital\u2019evich Kantorovich and Gennadii Shlemovich Rubinshtein. 1957. On a functional space and certain extremum problems. In Doklady Akademii Nauk. 115, 1058\u20131061.","journal-title":"Doklady Akademii Nauk."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963489"},{"key":"e_1_3_2_1_20_1","volume-title":"Spectrum estimation from samples. Ann. Statist., 45, 5","author":"Kong Weihao","year":"2017","unstructured":"Weihao Kong and Gregory Valiant . 2017. Spectrum estimation from samples. Ann. Statist., 45, 5 ( 2017 ), 10, 2218\u20132247. Weihao Kong and Gregory Valiant. 2017. Spectrum estimation from samples. Ann. Statist., 45, 5 (2017), 10, 2218\u20132247."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1170935"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/130934283"},{"key":"e_1_3_2_1_23_1","volume-title":"Traditional and Heavy Tailed Self Regularization in Neural Network Models. In","author":"Mahoney Michael","year":"2019","unstructured":"Michael Mahoney and Charles Martin . 2019. Traditional and Heavy Tailed Self Regularization in Neural Network Models. In 2019 , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds .). 97, 4284\u20134293. Michael Mahoney and Charles Martin. 2019. Traditional and Heavy Tailed Self Regularization in Neural Network Models. In 2019, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). 97, 4284\u20134293."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.16"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_3_2_1_26_1","volume-title":"Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition. In","author":"Musco Cameron","year":"2015","unstructured":"Cameron Musco and Christopher Musco . 2015. Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition. In 2015 . 1396\u20131404. Cameron Musco and Christopher Musco. 2015. Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition. In 2015. 1396\u20131404."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.105"},{"key":"e_1_3_2_1_28_1","volume-title":"Woodruff","author":"Musco Cameron","year":"2018","unstructured":"Cameron Musco , Praneeth Netrapalli , Aaron Sidford , Shashanka Ubaru , and David P . Woodruff . 2018 . Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness . 2018. Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P. Woodruff. 2018. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. 2018."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Beresford N. Parlett. 1998. The symmetric eigenvalue problem. SIAM.  Beresford N. Parlett. 1998. The symmetric eigenvalue problem. SIAM.","DOI":"10.1137\/1.9781611971163"},{"key":"e_1_3_2_1_30_1","volume-title":"Fast exact multiplication by the Hessian. Neural computation, 6, 1","author":"Pearlmutter Barak A.","year":"1994","unstructured":"Barak A. Pearlmutter . 1994. Fast exact multiplication by the Hessian. Neural computation, 6, 1 ( 1994 ), 147\u2013160. Barak A. Pearlmutter. 1994. Fast exact multiplication by the Hessian. Neural computation, 6, 1 (1994), 147\u2013160."},{"key":"e_1_3_2_1_31_1","volume-title":"The emergence of spectral universality in deep networks. In","author":"Pennington Jeffrey","year":"2018","unstructured":"Jeffrey Pennington , Samuel Schoenholz , and Surya Ganguli . 2018. The emergence of spectral universality in deep networks. In 2018 . 1924\u20131932. Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. 2018. The emergence of spectral universality in deep networks. In 2018. 1924\u20131932."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9220-1"},{"key":"e_1_3_2_1_33_1","volume-title":"Hanson-Wright inequality and sub-Gaussian concentration. Electronic Communications in Probability, 18","author":"Rudelson Mark","year":"2013","unstructured":"Mark Rudelson and Roman Vershynin . 2013. Hanson-Wright inequality and sub-Gaussian concentration. Electronic Communications in Probability, 18 ( 2013 ). Mark Rudelson and Roman Vershynin. 2013. Hanson-Wright inequality and sub-Gaussian concentration. Electronic Communications in Probability, 18 (2013)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129183194000842"},{"key":"e_1_3_2_1_35_1","volume-title":"Ahmed El Alaoui, and Benjamin Recht","author":"Simchowitz Max","year":"2018","unstructured":"Max Simchowitz , Ahmed El Alaoui, and Benjamin Recht . 2018 . Tight query complexity lower bounds for PCA via finite sample deformed wigner law. In 2018. 1249\u20131259. Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht. 2018. Tight query complexity lower bounds for PCA via finite sample deformed wigner law. In 2018. 1249\u20131259."},{"key":"e_1_3_2_1_36_1","volume-title":"The Eigenvalues of Mega-dimensional Matrices","author":"Skilling John","unstructured":"John Skilling . 1989. The Eigenvalues of Mega-dimensional Matrices . Springer Netherlands , 455\u2013466. John Skilling. 1989. The Eigenvalues of Mega-dimensional Matrices. Springer Netherlands, 455\u2013466."},{"key":"e_1_3_2_1_37_1","volume-title":"Querying a Matrix Through Matrix-Vector Products. In","author":"Sun Xiaoming","year":"2019","unstructured":"Xiaoming Sun , David P. Woodruff , Guang Yang , and Jialin Zhang . 2019. Querying a Matrix Through Matrix-Vector Products. In 2019 . 132, 94:1\u201394:16. Xiaoming Sun, David P. Woodruff, Guang Yang, and Jialin Zhang. 2019. Querying a Matrix Through Matrix-Vector Products. In 2019. 132, 94:1\u201394:16."},{"key":"e_1_3_2_1_38_1","volume-title":"Is Gauss quadrature better than Clenshaw\u2013Curtis? SIAM review, 50, 1","author":"Trefethen Lloyd N","year":"2008","unstructured":"Lloyd N Trefethen . 2008. Is Gauss quadrature better than Clenshaw\u2013Curtis? SIAM review, 50, 1 ( 2008 ), 67\u201387. Lloyd N Trefethen. 2008. Is Gauss quadrature better than Clenshaw\u2013Curtis? SIAM review, 50, 1 (2008), 67\u201387."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.49.10154"},{"key":"e_1_3_2_1_40_1","unstructured":"Weiran Wang and Miguel A Carreira-Perpin\u00e1n. 2013. Projection onto the probability simplex: An efficient algorithm with a simple proof and an application. arXiv preprint arXiv:1309.1541.  Weiran Wang and Miguel A Carreira-Perpin\u00e1n. 2013. Projection onto the probability simplex: An efficient algorithm with a simple proof and an application. arXiv preprint arXiv:1309.1541."},{"key":"e_1_3_2_1_41_1","volume-title":"The kernel polynomial method. Reviews of modern physics, 78, 1","author":"Alexander Wei\u00df","year":"2006","unstructured":"Alexander Wei\u00df e, Gerhard Wellein , Andreas Alvermann , and Holger Fehske . 2006. The kernel polynomial method. Reviews of modern physics, 78, 1 ( 2006 ), 275. Alexander Wei\u00df e, Gerhard Wellein, Andreas Alvermann, and Holger Fehske. 2006. The kernel polynomial method. Reviews of modern physics, 78, 1 (2006), 275."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_3_2_1_43_1","volume-title":"Mahoney","author":"Yao Zhewei","year":"2020","unstructured":"Zhewei Yao , Amir Gholami , Kurt Keutzer , and Michael W . Mahoney . 2020 . PyHessian: Neural Networks Through the Lens of the Hessian. In IEEE BigData . Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W. Mahoney. 2020. PyHessian: Neural Networks Through the Lens of the Hessian. In IEEE BigData."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520009","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":43,"alternative-id":["10.1145\/3519935.3520009","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520009","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}