{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T00:05:57Z","timestamp":1783296357352,"version":"3.54.6"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000138","name":"U.S. Department of Education","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000138","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2017698"],"award-info":[{"award-number":["2017698"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2026,3,31]]},"DOI":"10.1137\/24m1720895","type":"journal-article","created":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T13:43:21Z","timestamp":1772459001000},"page":"353-387","source":"Crossref","is-referenced-by-count":1,"title":["Hutchinson\u2019s Estimator is Bad at Kronecker-Trace-Estimation"],"prefix":"10.1137","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8564-7003","authenticated-orcid":true,"given":"Raphael A.","family":"Meyer","sequence":"first","affiliation":[{"name":"California Institute of Technology, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1688-9030","authenticated-orcid":true,"given":"Haim","family":"Avron","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,3,2]]},"reference":[{"key":"ref1","unstructured":"S. Aaronson, Introduction to Quantum Information Science Lecture Notes, 2018, https:\/\/www.scottaaronson.com\/qclec.pdf."},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"T. D. Ahle, M. Kapralov, J. B. Knudsen, R. Pagh, A. Velingker, D. P. Woodruff, and A. Zandieh, Oblivious sketching of high-degree polynomial kernels, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2020, pp. 141\u2013160, https:\/\/doi.org\/10.1137\/1.9781611975994.9.","DOI":"10.1137\/1.9781611975994.9"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944349"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"A. Bakshi, K. L. Clarkson, and D. P. Woodruff, Low-rank approximation with \\(1\/\\epsilon^{1\/3}\\) matrix-vector products, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2022, pp. 1130\u20131143, https:\/\/doi.org\/10.1145\/3519935.3519988.","DOI":"10.1145\/3519935.3519988"},{"key":"ref5","volume-title":"Matrix Mathematics: Theory, Facts, and Formulas","author":"Bernstein D. S.","year":"2011","edition":"2"},{"key":"ref6","unstructured":"M. Braverman, E. Hazan, M. Simchowitz, and B. Woodworth, The gradient complexity of linear regression, Proc. Mach. Learn. Res. (PMLR), 125 (2020), pp. 627\u2013647."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-022-01742-5"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/aa6dc3"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/draf043"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/20M1331718"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1063\/5.0099761"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/22M1494257"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-021-09525-9"},{"key":"ref14","unstructured":"E. Epperly, Stochastic Trace Estimation, https:\/\/www.ethanepperly.com\/index.php\/2023\/01\/26\/stochastic-trace-estimation\/, 2023."},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.030312"},{"key":"ref16","first-page":"3491","volume":"46","author":"Fika P.","year":"2017","journal-title":"Comm. Statist. Simulation Comput."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01395775"},{"key":"ref18","author":"Girard D.","year":"1987","journal-title":"Informatique et Math\u00e9matiques Appliqu\u2019ees de Grenoble"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2531"},{"key":"ref20","volume-title":"Inequalities","author":"Hardy G. H.","year":"1952"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-020-0932-7"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1080\/03610918908812806"},{"key":"ref23","first-page":"23741","volume":"34","author":"Jiang S.","year":"2021","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2015.07.007"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-021-00850-7"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"ref27","unstructured":"R. A. Meyer, Updates for Hutch++: Hutch++ for undergrads, 2021, https:\/\/ram900.com\/hutchplusplus\/#hutch_for_undergrads."},{"key":"ref28","unstructured":"R. A. Meyer, W. J. Swartworth, and D. Woodruff, Understanding the Kronecker matrix-vector complexity of linear algebra, in International Conference on Machine Learning (ICML), 2025."},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"D. Needell, W. Swartworth, and D. P. Woodruff, Testing positive semidefiniteness using linear measurements, in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2022, pp. 87\u201397, https:\/\/doi.org\/10.1109\/FOCS54457.2022.00016.","DOI":"10.1109\/FOCS54457.2022.00016"},{"key":"ref30","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M. A.","year":"2010"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.aop.2014.06.013"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/21M1447623"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9220-1"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-017-0880-z"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/3470566"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"W. Swartworth and D. P. Woodruff, Optimal eigenvalue approximation via sketching, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, ACM, New York, 2023, pp. 145\u2013155, https:\/\/doi.org\/10.1145\/3564246.3585102.","DOI":"10.1145\/3564246.3585102"},{"key":"ref37","unstructured":"J. A. Tropp and R. J. Webber, Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applications, preprint, arXiv:2306.12418, 2023."},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"R. Vershynin, Concentration inequalities for random tensors, Bernoulli, 26 (2020), pp. 3139\u20133162, https:\/\/doi.org\/10.3150\/20-BEJ1218.","DOI":"10.3150\/20-BEJ1218"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.5.020324"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_87"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T13:43:27Z","timestamp":1772891007000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1720895"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,2]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1137\/24M1720895"],"URL":"https:\/\/doi.org\/10.1137\/24m1720895","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,2]]}}}