{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T19:20:53Z","timestamp":1775503253383,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"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":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585102","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"145-155","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimal Eigenvalue Approximation via Sketching"],"prefix":"10.1145","author":[{"given":"William","family":"Swartworth","sequence":"first","affiliation":[{"name":"University of California at Los Angeles, Los Angeles, USA"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"An introduction to multivariate statistical analysis","author":"Anderson Theodore Wilbur","unstructured":"Theodore Wilbur Anderson . 1962. An introduction to multivariate statistical analysis . Wiley New York . Theodore Wilbur Anderson. 1962. An introduction to multivariate statistical analysis. Wiley New York."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.124"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00114"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.46"},{"key":"e_1_3_2_1_5_1","volume-title":"Sublinear Time Eigenvalue Approximation via Random Sampling. CoRR, abs\/2109.07647","author":"Bhattacharjee Rajarshi","year":"2021","unstructured":"Rajarshi Bhattacharjee , Gregory Dexter , Petros Drineas , Cameron Musco , and Archan Ray . 2021. Sublinear Time Eigenvalue Approximation via Random Sampling. CoRR, abs\/2109.07647 ( 2021 ). Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco, and Archan Ray. 2021. Sublinear Time Eigenvalue Approximation via Random Sampling. CoRR, abs\/2109.07647 (2021)."},{"key":"e_1_3_2_1_6_1","volume-title":"Conference on Learning Theory. 627\u2013647","author":"Braverman Mark","year":"2020","unstructured":"Mark Braverman , Elad Hazan , Max Simchowitz , and Blake Woodworth . 2020 . The gradient complexity of linear regression . In Conference on Learning Theory. 627\u2013647 . Mark Braverman, Elad Hazan, Max Simchowitz, and Blake Woodworth. 2020. The gradient complexity of linear regression. In Conference on Learning Theory. 627\u2013647."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520009"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"Kenneth","year":"2061","unstructured":"Kenneth L. Clarkson and David P. Woodruff. 2017. Low-Rank PSD Approximation in Input-Sparsity Time . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain, Hotel Porta Fira, January 16-19, Philip N. Klein (Ed.). SIAM , 2061 \u20132072. Kenneth L. Clarkson and David P. Woodruff. 2017. Low-Rank PSD Approximation in Input-Sparsity Time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, Philip N. Klein (Ed.). SIAM, 2061\u20132072."},{"key":"e_1_3_2_1_9_1","unstructured":"Michael B Cohen Jelani Nelson and David P Woodruff. 2015. Optimal approximate matrix product in terms of stable rank. arXiv preprint arXiv:1507.02268. \t\t\t\t  Michael B Cohen Jelani Nelson and David P Woodruff. 2015. Optimal approximate matrix product in terms of stable rank. arXiv preprint arXiv:1507.02268."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.67"},{"key":"e_1_3_2_1_11_1","volume-title":"Optimal Sketching for Trace Estimation. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021","author":"Jiang Shuli","year":"2021","unstructured":"Shuli Jiang , Hai Pham , David P. Woodruff , and Qiuyi (Richard) Zhang . 2021 . Optimal Sketching for Trace Estimation. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021 , NeurIPS 2021, December 6-14, 2021, virtual, Marc\u2019Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 23741\u201323753. Shuli Jiang, Hai Pham, David P. Woodruff, and Qiuyi (Richard) Zhang. 2021. Optimal Sketching for Trace Estimation. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, Marc\u2019Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 23741\u201323753."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/009117906000000205"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(82)90080-X"},{"key":"e_1_3_2_1_14_1","volume-title":"Faster algorithms for rectangular matrix multiplication. In 2012 IEEE 53rd annual symposium on foundations of computer science. 514\u2013523","author":"Gall Fran\u00e7ois Le","unstructured":"Fran\u00e7ois Le Gall . 2012. Faster algorithms for rectangular matrix multiplication. In 2012 IEEE 53rd annual symposium on foundations of computer science. 514\u2013523 . Fran\u00e7ois Le Gall. 2012. Faster algorithms for rectangular matrix multiplication. In 2012 IEEE 53rd annual symposium on foundations of computer science. 514\u2013523."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634188"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1152255"},{"key":"e_1_3_2_1_17_1","volume-title":"4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference","author":"Meyer Raphael A.","year":"2021","unstructured":"Raphael A. Meyer , Cameron Musco , Christopher Musco , and David P. Woodruff . 2021. Hutch++: Optimal Stochastic Trace Estimation . In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference , January 11-12, 2021 , Hung Viet Le and Valerie King (Eds.). SIAM, 142\u2013155. Raphael A. Meyer, Cameron Musco, Christopher Musco, and David P. Woodruff. 2021. Hutch++: Optimal Stochastic Trace Estimation. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, Hung Viet Le and Valerie King (Eds.). SIAM, 142\u2013155."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.16"},{"key":"e_1_3_2_1_19_1","volume-title":"Woodruff","author":"Needell Deanna","year":"2022","unstructured":"Deanna Needell , William Swartworth , and David P . Woodruff . 2022 . Testing Positive Semidefiniteness Using Linear Measurements. CoRR , abs\/2204.03782 (2022). Deanna Needell, William Swartworth, and David P. Woodruff. 2022. Testing Positive Semidefiniteness Using Linear Measurements. CoRR, abs\/2204.03782 (2022)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3470566"},{"key":"e_1_3_2_1_21_1","unstructured":"Roman Vershynin. 2010. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027. \t\t\t\t  Roman Vershynin. 2010. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027."},{"key":"e_1_3_2_1_22_1","volume-title":"Spectral norm of products of random and deterministic matrices. Probability theory and related fields, 150, 3-4","author":"Vershynin Roman","year":"2011","unstructured":"Roman Vershynin . 2011. Spectral norm of products of random and deterministic matrices. Probability theory and related fields, 150, 3-4 ( 2011 ), 471\u2013509. Roman Vershynin. 2011. Spectral norm of products of random and deterministic matrices. Probability theory and related fields, 150, 3-4 (2011), 471\u2013509."},{"key":"e_1_3_2_1_23_1","volume-title":"High-dimensional probability: An introduction with applications in data science. 47","author":"Vershynin Roman","unstructured":"Roman Vershynin . 2018. High-dimensional probability: An introduction with applications in data science. 47 , Cambridge university press . Roman Vershynin. 2018. High-dimensional probability: An introduction with applications in data science. 47, Cambridge university press."},{"key":"e_1_3_2_1_24_1","volume-title":"19th International Conference on Database Theory, ICDT 2016","author":"Woodruff David P.","year":"2016","unstructured":"David P. Woodruff . 2016 . New Algorithms for Heavy Hitters in Data Streams (Invited Talk) . In 19th International Conference on Database Theory, ICDT 2016 , Bordeaux, France , March 15-18, 2016, Wim Martens and Thomas Zeume (Eds.) (LIPIcs, Vol. 48). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 4:1\u20134:12. David P. Woodruff. 2016. New Algorithms for Heavy Hitters in Data Streams (Invited Talk). In 19th International Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15-18, 2016, Wim Martens and Thomas Zeume (Eds.) (LIPIcs, Vol. 48). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 4:1\u20134:12."},{"key":"e_1_3_2_1_25_1","unstructured":"David P Woodruff Fred Zhang and Qiuyi Zhang. 2022. Optimal Query Complexities for Dynamic Trace Estimation. arXiv preprint arXiv:2209.15219. \t\t\t\t  David P Woodruff Fred Zhang and Qiuyi Zhang. 2022. Optimal Query Complexities for Dynamic Trace Estimation. arXiv preprint arXiv:2209.15219."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":25,"alternative-id":["10.1145\/3564246.3585102","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585102","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}