{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:01Z","timestamp":1787337481016,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We consider the problem of online sublinear expander reconstruction and its relation to random walks in \u201cnoisy\" expanders. Given access to an adjacency list representation of a bounded-degree graph $G$, we want to convert this graph into a bounded-degree expander $G'$ changing $G$ as little as possible. The graph $G'$ will be output by a distributed filter: this is a sublinear time procedure that, given a query vertex, outputs all its neighbors in $G'$ and can do so even in a distributed manner, ensuring consistency in all the answers. One of the main tools in our analysis is a result on the behavior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small unknown graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander part will have fast mixing properties, in the general setting of irreducible finite Markov chains. We also design sublinear time procedures to distinguish vertices of the expander part from those in the noise part and use this procedure in the reconstruction algorithm.<\/jats:p>","DOI":"10.1137\/110837863","type":"journal-article","created":{"date-parts":[[2013,2,14]],"date-time":"2013-02-14T16:34:55Z","timestamp":1360859695000},"page":"305-323","source":"Crossref","is-referenced-by-count":7,"title":["Noise Tolerance of Expanders and Sublinear Expansion Reconstruction"],"prefix":"10.1137","volume":"42","author":[{"given":"Satyen","family":"Kale","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Peres","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,2,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9075-9"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/060667177"},{"key":"atypb5","unstructured":"R. Andersen (2008),\n                      A local algorithm for finding dense subgraphs\n                      , in Proceedings of the 19th Annual Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, pp. 1003-1009."},{"key":"atypb6","unstructured":"R. Andersen and K. Lang (2008),\n                      An algorithm for improving graph partitions\n                      , in Proceedings of the 19th Annual Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, pp. 651-660."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"R. Andersen, F. R. K. Chung, and K. Lang (2006),\n                      Local graph partitioning using pagerank vectors\n                      , in Proceedings of the 47th Annual Foundations of Computer Science (FOCS), pp. 475-486.","DOI":"10.1109\/FOCS.2006.44"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20300"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White (2000),\n                      Testing that distributions are close\n                      , in Proceedings of the 41st Annual Foundations of Computer Science (FOCS), pp. 259-269.","DOI":"10.1109\/SFCS.2000.892113"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.10.018"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"A. Czumaj and C. Sohler (2007),\n                      Testing expansion in bounded degree graphs\n                      , in Proceedings of the 48th Annual Foundations of Computer Science (FOCS), pp. 570-578.","DOI":"10.1109\/FOCS.2007.33"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/070681831"},{"key":"atypb13","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Euro. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"O. Gabber and Z. Galil (1979),\n                      Explicit constructions of linear size superconcentrators\n                      , in Proceedings of the 20th Annual Foundations of Computer Science (FOCS), pp. 364-370.","DOI":"10.1109\/SFCS.1979.16"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"O. Goldreich (1998),\n                      Combinatorial property testing-a survey\n                      , in Randomization Methods in Algorithm Design, P. M. Pardalos, S. Rajasekaran, and J. Rolim, eds., AMS, Providence, RI, pp. 45-60.","DOI":"10.1090\/dimacs\/043\/04"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"atypb17","unstructured":"O. Goldreich and D. Ron (2000),\n                      On Testing Expansion in Bounded-Degree Graphs\n                      , ECCC, TR00-020."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"S. Kale, Y. Peres, and C. Seshadhri (2008),\n                      Noise tolerance of expanders and sublinear expander reconstruction\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 719-728.","DOI":"10.1109\/FOCS.2008.65"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/100802980"},{"key":"atypb22","first-page":"85","author":"Lov\u00e1sz L.","year":"1998","journal-title":"Theoret. Comput. Sci., AMS, Providence, RI"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.09.002"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"D. Ron (2001),\n                      Property testing\n                      , in Handbook of Randomized Computing, Vol. II, S. Rajasekaran, P. M. Pardalos, J. H. Reif, and J. Rolim, eds., Kluwer, Dordrecht, pp. 597-649.","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"atypb27","unstructured":"R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie (2011),\n                      Fast local computation algorithms\n                      , in Proceedings of the 2nd Annual Innovations in Computer Science (ICS)."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/080728561"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000390"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110837863","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:27Z","timestamp":1787335947000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110837863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110837863"],"URL":"https:\/\/doi.org\/10.1137\/110837863","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}