{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T19:26:32Z","timestamp":1749497192769,"version":"3.38.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T00:00:00Z","timestamp":1318982400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,3]]},"DOI":"10.1007\/s00037-011-0022-4","type":"journal-article","created":{"date-parts":[[2011,10,18]],"date-time":"2011-10-18T06:30:38Z","timestamp":1318919438000},"page":"129-192","source":"Crossref","is-referenced-by-count":8,"title":["Hierarchy Theorems for Property Testing"],"prefix":"10.1007","volume":"21","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eyal","family":"Rozenberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,10,19]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1002\/rsa.10056","volume":"21","author":"N. Alon","year":"2002","unstructured":"Alon N.: Testing Subgraphs of Large Graphs. Random Structures and Algorithms. 21, 359\u2013370 (2002)","journal-title":"Random Structures and Algorithms."},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon N., Babai L., Itai A.: A fast and Simple Randomized Algorithm for the Maximal Independent Set Problem. J. of Algorithms. 7, 567\u2013583 (1986)","journal-title":"J. of Algorithms."},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s004930070001","volume":"20","author":"N. Alon","year":"2000","unstructured":"Alon N., Fischer E., Krivelevich M., Szegedy M.: Efficient Testing of Large Graphs. Combinatorica. 20, 451\u2013476 (2000)","journal-title":"Combinatorica."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"N. Alon, E. Fischer, I. Newman & A. Shapira. A Combinatorial Characterization of the Testable Graph Properties: It\u2019s All About Regularity. In 38th STOC, pages 251\u2013260, 2006.","DOI":"10.1145\/1132516.1132555"},{"issue":"3","key":"22_CR5","first-page":"354","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon N., Goldreich O., Hastad J., Peralta R.: Simple constructions of almost k-wise independent random variables. Journal of Random structures and Algorithms. 3(3), 354\u2013482 (1992)","journal-title":"Journal of Random structures and Algorithms."},{"key":"22_CR6","first-page":"354","volume":"69","author":"N. Alon","year":"2004","unstructured":"Alon N., Shapira A.: Testing Subgraphs in Directed Graphs. JCSS. 69, 354\u2013482 (2004)","journal-title":"JCSS."},{"key":"22_CR7","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1017\/S0963548306007759","volume":"15","author":"N. Alon","year":"2006","unstructured":"Alon N., Shapira A.: A Characterization of Easily Testable Induced Subgraphs. Combinatorics Probability and Computing. 15, 791\u2013805 (2006)","journal-title":"Combinatorics Probability and Computing."},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/050633445","volume":"38","author":"N. Alon","year":"2008","unstructured":"Alon N., Shapira A.: Every Monotone Graph Property is Testable. SIAM Journal on Computing. 38, 505\u2013522 (2008)","journal-title":"SIAM Journal on Computing."},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"L. Avigad & O. Goldreich. Testing Graph Blow-Up. Unpublished manuscript, 2010. Available from http:\/\/www.wisdom.weizmann.ac.il\/~oded\/p_lidor.html .","DOI":"10.1007\/978-3-642-22935-0_33"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"I. Benjamini, O. Schramm & A. Shapira. Every Minor-Closed Property of Sparse Graphs is Testable. In 40th STOC, pages 393\u2013402, 2008.","DOI":"10.1145\/1374376.1374433"},{"issue":"3","key":"22_CR11","first-page":"549","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum M., Luby M., Rubinfeld R.: Self-Testing\/Correcting with Applications to Numerical Problems. JCSS. 47(3), 549\u2013595 (1993)","journal-title":"JCSS."},{"issue":"1","key":"22_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2005","unstructured":"Ben-Sasson E., Harsha P., Raskhodnikova S.: 3CNF Properties Are Hard to Test. SIAM Journal on Computing. 35(1), 1\u201321 (2005)","journal-title":"SIAM Journal on Computing."},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"A. Bogdanov, K. Obata & L. Trevisan. A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. In 43rd FOCS, pages 93\u2013102, 2002.","DOI":"10.1109\/SFCS.2002.1181886"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"C. Borgs, J. Chayes, L. Lov\u00e1sz, V.T. S\u00f3s, B. Szegedy & K. Vesztergombi. Graph Limits and Parameter Testing. In 38th STOC, pages 261\u2013270, 2006.","DOI":"10.1145\/1132516.1132556"},{"issue":"3","key":"22_CR15","first-page":"717","volume":"60","author":"F. Ergun","year":"2000","unstructured":"Ergun F., Kannan S., Kumar S.R., Rubinfeld R., Viswanathan M.: Spot-Checkers. JCSS. 60(3), 717\u2013751 (2000)","journal-title":"JCSS."},{"issue":"1","key":"22_CR16","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/070680795","volume":"38","author":"E. Fischer","year":"2008","unstructured":"Fischer E., Matsliah A.: Testing Graph Isomorphism. SIAM J. Comput. 38(1), 207\u2013225 (2008)","journal-title":"SIAM J. Comput."},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"E. Fischer & E. Rozenberg. Inflatable Graph Properties and Natural Property Tests. In 15th RANDOM, Springer, LNCS 6845, pages 542\u2013554, 2011.","DOI":"10.1007\/978-3-642-22935-0_46"},{"issue":"3","key":"22_CR18","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"Goldreich O., Goldwasser S., Lehman E., Ron D., Samorodnitsky A.: Testing Monotonicity. Combinatorica. 20(3), 301\u2013337 (2000)","journal-title":"Combinatorica."},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"O.Goldreich, S. Goldwasser & D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, Vol. 45 (4), pages 653\u2013750, July 1998.","DOI":"10.1145\/285055.285060"},{"key":"22_CR20","unstructured":"O. Goldreich, M. Krivelevich, I. Newman & E. Rozenberg. Hierarchy Theorems for Property Testing. ECCC, TR08-097, 2008."},{"issue":"2","key":"22_CR21","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O. Goldreich","year":"2002","unstructured":"Goldreich O., Ron D.: Property Testing in Bounded Degree Graphs. Algorithmica. 32(2), 302\u2013343 (2002)","journal-title":"Algorithmica."},{"issue":"3","key":"22_CR22","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"O. Goldreich","year":"1999","unstructured":"Goldreich O., Ron D.: A Sublinear Bipartitness Tester for Bounded Degree Graphs. Combinatorica. 19(3), 335\u2013373 (1999)","journal-title":"Combinatorica."},{"key":"22_CR23","doi-asserted-by":"crossref","unstructured":"O. Goldreich & L. Trevisan. Three theorems regarding testing graph properties. Random Structures and Algorithms, Vol. 23 (1), pages 23\u201357, August 2003.","DOI":"10.1002\/rsa.10078"},{"key":"22_CR24","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/s00037-008-0239-z","volume":"17","author":"O. Lachish","year":"2008","unstructured":"Lachish O., Newman I., Shapira A.: Space Complexity vs. Query Complexity. Computational Complexity. 17, 70\u201393 (2008)","journal-title":"Query Complexity. Computational Complexity."},{"key":"22_CR25","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor J., Naor M.: Small-bias Probability Spaces: Efficient Constructions and Applications. SIAM J. on Computing. 22, 838\u2013856 (1993)","journal-title":"SIAM J. on Computing."},{"issue":"1","key":"22_CR26","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1002\/rsa.10067","volume":"22","author":"M. Parnas","year":"2003","unstructured":"Parnas M., Ron D., Rubinfeld R.: Testing Membership in Parenthesis Laguages. Random Structures and Algorithms. 22(1), 98\u2013138 (2003)","journal-title":"Random Structures and Algorithms."},{"key":"22_CR27","unstructured":"O. Pikhurko. An Analytic Approach to Stability. Manuscript, 2009. Available from http:\/\/arxiv.org\/abs\/0812.0214 ."},{"issue":"3","key":"22_CR28","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1561\/2200000004","volume":"1","author":"D. Ron","year":"2008","unstructured":"Ron D.: Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning. 1(3), 307\u2013402 (2008)","journal-title":"Foundations and Trends in Machine Learning."},{"issue":"2","key":"22_CR29","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D. Ron","year":"2009","unstructured":"Ron D.: Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in TCS. 5(2), 73\u2013205 (2009)","journal-title":"Foundations and Trends in TCS."},{"issue":"2","key":"22_CR30","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld R., Sudan M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing. 25(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing."},{"key":"22_CR31","unstructured":"R. Shaltiel. Recent Developments in Explicit Constructions of Extractors. In Current Trends in Theoretical Computer Science: The Challenge of the New Century, Vol 1: Algorithms and Complexity, World scietific, 2004. Preliminary version in Bulletin of the EATCS 77, pages 67\u201395, 2002."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0022-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0022-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0022-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:24:42Z","timestamp":1741825482000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0022-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,19]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["22"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0022-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2011,10,19]]}}}