{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:14Z","timestamp":1787340314347,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model [O. Goldreich and D. Ron, On Testing Expansion in Bounded-Degree Graphs, Technical report TR00-020, ECCC, Potsdam, Germany, 2000]. We give a property tester that takes as input a graph with degree bound d, an expansion bound $\\alpha$, and a parameter $\\varepsilon&gt;0$. The tester accepts the graph with high probability if its expansion is more than $\\alpha$, and rejects it with high probability if it is $\\varepsilon$-far from any graph with expansion $\\alpha'$ with degree bound d, where $\\alpha'&lt;\\alpha$ is a function of $\\alpha$. For edge expansion, we obtain $\\alpha'=\\Omega(\\frac{\\alpha^2}{d})$, and for vertex expansion, we obtain $\\alpha'=\\Omega(\\frac{\\alpha^2}{d^2})$. In either case, the algorithm runs in time $\\widetilde{O}(\\frac{n^{(1+\\mu)\/2}d^2}{\\varepsilon\\alpha^2})$ for any fixed $\\mu&gt;0$.<\/jats:p>","DOI":"10.1137\/100802980","type":"journal-article","created":{"date-parts":[[2011,6,9]],"date-time":"2011-06-09T19:13:44Z","timestamp":1307646824000},"page":"709-720","source":"Crossref","is-referenced-by-count":18,"title":["An Expansion Tester for Bounded Degree Graphs"],"prefix":"10.1137","volume":"40","author":[{"given":"Satyen","family":"Kale","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,6,9]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/060667177"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.10.018"},{"key":"R4","unstructured":"F. Chung,\n                      Spectral Graph Theory\n                      , CBMS Reg. Conf. Ser. Math. 92, AMS, Providence, RI, 1992. Available at http:\/\/www.math.ucsd.edu\/~fan\/research\/revised.html."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Czumaj and C. Sohler,\n                      Testing expansion in bounded degree graphs\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007, pp. 570\u2013578.","DOI":"10.1109\/FOCS.2007.33"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/070681831"},{"key":"R7","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"O. Goldreich,\n                      Introduction to Testing Graph Properties\n                      , Technical report TR10-082, ECCC, Potsdam, Germany, 2010.","DOI":"10.1007\/978-3-642-16367-8_7"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"R11","unstructured":"O. Goldreich and D. Ron,\n                      On Testing Expansion in Bounded-Degree Graphs\n                      , Technical report TR00-020, ECCC, Potsdam, Germany, 2000."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"R13","unstructured":"S. Kale and C. Seshadhri,\n                      Testing Expansion in Bounded Degree Graphs\n                      , Technical report TR07-076, ECCC, Potsdam, Germany, 2007."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"S. Kale and C. Seshadhri,\n                      An expansion tester for bounded degree graphs\n                      , in Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP(I)), Lecture Notes in Comput. Sci. 5125, Springer-Verlag, Berlin, 2008, pp. 527\u2013538.","DOI":"10.1007\/978-3-540-70575-8_43"},{"key":"R15","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 2000."},{"key":"R16","unstructured":"A. Nachmias and A. Shapira,\n                      Testing the Expansion of a Graph\n                      , Technical report TR07-118, ECCC, Potsdam, Germany, 2007."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"D. Ron,\n                      Property testing\n                      , in Handbook on Randomized Computing, II, Comb. Optim. 9, Kluwer Academic, Dordrecht, The Netherlands, 2001, pp. 597\u2013649.","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1561\/0400000029"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. Sinclair,\n                      Algorithms for Random Generation and Counting: A Markov Chain Approach\n                      , Progr. Theoret. Comput. Sci., Birkh\u00e4user, Boston, 1993.","DOI":"10.1007\/978-1-4612-0323-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100802980","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:32Z","timestamp":1787336972000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100802980"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100802980"],"URL":"https:\/\/doi.org\/10.1137\/100802980","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}