{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:06:33Z","timestamp":1772499993235,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_87","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"1051-1062","source":"Crossref","is-referenced-by-count":10,"title":["Optimal Query Complexity for Estimating the Trace of a Matrix"],"prefix":"10.1007","author":[{"given":"Karl","family":"Wimmer","sequence":"first","affiliation":[]},{"given":"Yi","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Peng","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"87_CR1","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/s004530010062","volume":"29","author":"M.J. Atallah","year":"2001","unstructured":"Atallah, M.J., Chyzak, F., Dumas, P.: A randomized algorithm for approximate string matching. Algorithmica\u00a029(3), 468\u2013486 (2001)","journal-title":"Algorithmica"},{"issue":"18","key":"87_CR2","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1016\/j.ipl.2013.06.005","volume":"113","author":"M.J. Atallah","year":"2013","unstructured":"Atallah, M.J., Grigorescu, E., Wu, Y.: A lower-variance randomized algorithm for approximate string matching. Information Processing Letters\u00a0113(18), 690\u2013692 (2013)","journal-title":"Information Processing Letters"},{"issue":"2","key":"87_CR3","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/1944345.1944349","volume":"58","author":"H. Avron","year":"2011","unstructured":"Avron, H., Toledo, S.: Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Journal of the ACM (JACM)\u00a058(2), 8 (2011)","journal-title":"Journal of the ACM (JACM)"},{"key":"87_CR4","unstructured":"Avron, H.: Counting triangles in large graphs using randomized matrix trace estimation. In: Proceedings of KDD-LDMTA, vol.\u00a010 (2010)"},{"issue":"23","key":"87_CR5","doi-asserted-by":"publisher","first-page":"3631","DOI":"10.1103\/PhysRevLett.70.3631","volume":"70","author":"D.A. Drabold","year":"1993","unstructured":"Drabold, D.A., Sankey, O.F.: Maximum entropy approach for linear scaling in the electronic structure problem. Physical Review Letters\u00a070(23), 3631 (1993)","journal-title":"Physical Review Letters"},{"issue":"3","key":"87_CR6","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1080\/03610918908812806","volume":"18","author":"M.F. Hutchinson","year":"1989","unstructured":"Hutchinson, M.F.: A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statistics-Simulation and Computation\u00a018(3), 1059\u20131076 (1989)","journal-title":"Communications in Statistics-Simulation and Computation"},{"key":"87_CR7","doi-asserted-by":"crossref","unstructured":"Iitaka, T., Ebisuzaki, T.: Random phase vector for calculating the trace of a large matrix. arXiv preprint cond-mat\/0401202 (2004)","DOI":"10.1103\/PhysRevE.69.057701"},{"key":"87_CR8","doi-asserted-by":"crossref","unstructured":"Li, Y., Nguy\u00ean, H.L., Woodruff, D.P.: On sketching matrix norms and the top singular vector. In: Proceedings of the Twenty Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (2014)","DOI":"10.1137\/1.9781611973402.114"},{"key":"87_CR9","doi-asserted-by":"crossref","unstructured":"Roosta-Khorasani, F., Ascher, U.: Improved bounds on sample size for implicit matrix trace estimators (2013)","DOI":"10.1007\/s10208-014-9220-1"},{"issue":"4","key":"87_CR10","doi-asserted-by":"publisher","first-page":"4822","DOI":"10.1103\/PhysRevE.56.4822","volume":"56","author":"R.N. Silver","year":"1997","unstructured":"Silver, R.N., R\u00f6der, H.: Calculation of densities of states and spectral functions by chebyshev recursion and maximum entropy. Physical Review E\u00a056(4), 4822 (1997)","journal-title":"Physical Review E"},{"key":"87_CR11","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E.: Fast counting of triangles in large real networks without counting: Algorithms and laws. In: Eighth IEEE International Conference on Data Mining, ICDM 2008, pp. 608\u2013617. IEEE (2008)","DOI":"10.1109\/ICDM.2008.72"},{"issue":"15","key":"87_CR12","doi-asserted-by":"publisher","first-page":"10154","DOI":"10.1103\/PhysRevB.49.10154","volume":"49","author":"L.-W. Wang","year":"1994","unstructured":"Wang, L.-W.: Calculating the density of states and optical-absorption spectra of large quantum systems by the plane-wave moments method. Physical Review B\u00a049(15), 10154 (1994)","journal-title":"Physical Review B"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_87","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:04:35Z","timestamp":1558922675000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_87"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_87","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}