{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:18:19Z","timestamp":1781075899593,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["RBSI14Q743"],"award-info":[{"award-number":["RBSI14Q743"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"publisher","award":["Proj. CAEPAE"],"award-info":[{"award-number":["Proj. CAEPAE"]}],"id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["DMAP 680153"],"award-info":[{"award-number":["DMAP 680153"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Google Focused Award"],"award-info":[{"award-number":["Google Focused Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["Dipartimenti di Eccellenza 2018-2022"],"award-info":[{"award-number":["Dipartimenti di Eccellenza 2018-2022"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00224-019-09921-3","type":"journal-article","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T16:07:24Z","timestamp":1554480444000},"page":"444-466","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On Approximating the Stationary Distribution of Time-Reversible Markov Chains"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5211-2264","authenticated-orcid":false,"given":"Marco","family":"Bressan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Enoch","family":"Peserico","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Pretto","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"issue":"4","key":"9921_CR1","doi-asserted-by":"publisher","first-page":"1470","DOI":"10.1214\/09-AAP656","volume":"20","author":"N Alon","year":"2010","unstructured":"Alon, N., Gurel-Gurevich, O., Lubetzky, E.: Choice-memory tradeoff in allocations. Ann. Appl. Probab. 20(4), 1470\u20131511 (2010)","journal-title":"Ann. Appl. Probab."},{"key":"9921_CR2","doi-asserted-by":"crossref","unstructured":"Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics: Foundations and Recent Developments, vol. 1. World Scientific Publishing Co., Inc, Singapore (2011)","DOI":"10.1142\/7438"},{"key":"9921_CR3","unstructured":"Banerjee, S., Lofgren, P.: Fast Bidirectional Probability Estimation in Markov Models. In: Proceedings Of NIPS, pp. 1423\u20131431 (2015)"},{"issue":"3","key":"9921_CR4","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0378-8733(01)00038-7","volume":"23","author":"P Bonacich","year":"2001","unstructured":"Bonacich, P., Lloyd, P.: Eigenvector-like measures of centrality for asymmetric relations. Soc. Netw. 23(3), 191\u2013201 (2001)","journal-title":"Soc. Netw."},{"issue":"1-2","key":"9921_CR5","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1080\/15427951.2013.802752","volume":"10","author":"C Borgs","year":"2014","unstructured":"Borgs, C., Brautbar, M., Chayes, J. T., Teng, S.: Multiscale matrix sampling and sublinear-time PageRank computation. Internet Math. 10(1-2), 20\u201348 (2014)","journal-title":"Internet Math."},{"key":"9921_CR6","doi-asserted-by":"crossref","unstructured":"Borgs, C., Brautbar, M., Chayes, J. T., Teng, S. H.: A Sublinear Time Algorithm for PageRank Computations. In: Proceedings Of WAW, pp. 41\u201353. Springer (2012)","DOI":"10.1007\/978-3-642-30541-2_4"},{"key":"9921_CR7","doi-asserted-by":"crossref","unstructured":"Bressan, M., Peserico, E., Pretto, L.: Brief Announcement: On Approximating PageRank Locally with Sublinear Query Complexity. In: Proceedings Of ACM SPAA, pp. 87\u201389 (2018)","DOI":"10.1145\/3210377.3210664"},{"key":"9921_CR8","doi-asserted-by":"crossref","unstructured":"Bressan, M., Peserico, E., Pretto, L.: Sublinear Algorithms for Local Graph Centrality Estimation. In: Proceedings Of IEEE FOCS, pp. 709\u2013718 (2018)","DOI":"10.1109\/FOCS.2018.00073"},{"key":"9921_CR9","unstructured":"Chung, K. M., Lam, H., Liu, Z., Mitzenmacher, M.: Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified. In: Proceedings Of STACS, pp. 124\u2013135 (2012)"},{"issue":"1","key":"9921_CR10","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1214\/aop\/1176996452","volume":"3","author":"DA Freedman","year":"1975","unstructured":"Freedman, D. A.: On tail probabilities for martingales. Ann. Probab. 3(1), 100\u2013118 (1975)","journal-title":"Ann. Probab."},{"key":"9921_CR11","volume-title":"Matrix Computations.","author":"GH Golub","year":"2012","unstructured":"Golub, G. H., Van Loan, C. F.: Matrix Computations. Johns Hopkins University Press, Baltimore (2012)"},{"issue":"1","key":"9921_CR12","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","volume":"57","author":"WK Hastings","year":"1970","unstructured":"Hastings, W. K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97\u2013109 (1970)","journal-title":"Biometrika"},{"key":"9921_CR13","unstructured":"Lee, C. E., Ozdaglar, A., Shah, D.: Computing the Stationary Distribution, Locally. In: Proceedings Of NIPS, pp. 1376\u20131384 (2013)"},{"key":"9921_CR14","unstructured":"Lee, C. E., Ozdaglar, A. E., Shah, D.: Solving systems of linear equations: Locally and asynchronously. arXiv:\n1411.2647\n\n (2014)"},{"key":"9921_CR15","doi-asserted-by":"crossref","unstructured":"Levin, D. A., Peres, Y., Wilmer, E. L.: Markov Chains and Mixing Times. American Mathematical Society (2009)","DOI":"10.1090\/mbk\/058"},{"key":"9921_CR16","doi-asserted-by":"crossref","unstructured":"Lofgren, P., Banerjee, S., Goel, A.: Bidirectional PageRank Estimation: from Average-Case to Worst-Case. In: Proceedings Of WAW, pp. 164\u2013176 (2015)","DOI":"10.1007\/978-3-319-26784-5_13"},{"key":"9921_CR17","doi-asserted-by":"crossref","unstructured":"Lofgren, P. A., Banerjee, S., Goel, A., Seshadhri, C.: FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs. In: Proceedings Of ACM KDD, pp. 1436\u20131445 (2014)","DOI":"10.1145\/2623330.2623745"},{"key":"9921_CR18","doi-asserted-by":"crossref","unstructured":"Motwani, R., Panigrahy, R., Xu, Y.: Estimating Sum by Weighted Sampling. In: Proceedings Of ICALP, pp. 53\u201364 (2007)","DOI":"10.1007\/978-3-540-73420-8_7"},{"key":"9921_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"9921_CR20","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff\u2013Hoeffding bounds. SIAM J. Comput. 26(2), 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9921_CR21","doi-asserted-by":"publisher","first-page":"1562","DOI":"10.1137\/100791075","volume":"25","author":"R Rubinfeld","year":"2011","unstructured":"Rubinfeld, R., Shapira, A.: Sublinear time algorithms. SIAM J. Discret. Math. 25(4), 1562\u20131588 (2011)","journal-title":"SIAM J. Discret. Math."},{"key":"9921_CR22","doi-asserted-by":"crossref","unstructured":"Shyamkumar, N., Banerjee, S., Lofgren, P.: Sublinear Estimation of a Single Element in Sparse Linear Systems. In: 2016 Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 856\u2013860 (2016)","DOI":"10.1109\/ALLERTON.2016.7852323"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09921-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09921-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09921-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T23:08:41Z","timestamp":1585955321000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09921-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,5]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9921"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09921-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,5]]},"assertion":[{"value":"5 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}