{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:54:30Z","timestamp":1787500470523,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642036842","type":"print"},{"value":"9783642036859","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_38","type":"book-chapter","created":{"date-parts":[[2009,8,20]],"date-time":"2009-08-20T22:39:51Z","timestamp":1250807991000},"page":"504-519","source":"Crossref","is-referenced-by-count":5,"title":["Hierarchy Theorems for Property Testing"],"prefix":"10.1007","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eyal","family":"Rozenberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"38_CR1","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.\u00a0of Algorithms\u00a07, 567\u2013583 (1986)","journal-title":"J. of Algorithms"},{"key":"38_CR2","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\u00a020, 451\u2013476 (2000)","journal-title":"Combinatorica"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A Combinatorial Characterization of the Testable Graph Properties: It\u2019s All About Regularity. In: 38th STOC, pp. 251\u2013260 (2006)","DOI":"10.1145\/1132516.1132555"},{"issue":"3","key":"38_CR4","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","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\u00a03(3), 289\u2013304 (1992)","journal-title":"Journal of Random structures and Algorithms"},{"key":"38_CR5","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\u00a038, 505\u2013522 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Schramm, O., Shapira, A.: Every Minor-Closed Property of Sparse Graphs is Testable. In: 40th STOC, pp. 393\u2013402 (2008)","DOI":"10.1145\/1374376.1374433"},{"issue":"3","key":"38_CR7","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\u00a047(3), 549\u2013595 (1993)","journal-title":"JCSS"},{"issue":"1","key":"38_CR8","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\u00a035(1), 1\u201321 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Obata, K., Trevisan, L.: A lower bound for testing 3-colorability in bounded-degree graphs. In: 43rd FOCS, pp. 93\u2013102 (2002)","DOI":"10.1109\/SFCS.2002.1181886"},{"issue":"3","key":"38_CR10","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\u00a060(3), 717\u2013751 (2000)","journal-title":"JCSS"},{"key":"38_CR11","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science\u00a075, 97\u2013126 (2001)"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"Fischer, E., Matsliah, A.: Testing Graph Isomorphism. In: 17th SODA, pp. 299\u2013308 (2006)","DOI":"10.1145\/1109557.1109591"},{"issue":"3","key":"38_CR13","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\u00a020(3), 301\u2013337 (2000)","journal-title":"Testing Monotonicity. Combinatorica"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM, 653\u2013750 (July 1998)","DOI":"10.1145\/285055.285060"},{"key":"38_CR15","unstructured":"Goldreich, O., Krivelevich, M., Newman, I., Rozenberg, E.: Hierarchy Theorems for Property Testing. ECCC, TR08-097 (2008)"},{"issue":"2","key":"38_CR16","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\u00a032(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"issue":"3","key":"38_CR17","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\u00a019(3), 335\u2013373 (1999)","journal-title":"Combinatorica"},{"issue":"1","key":"38_CR18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/rsa.10078","volume":"23","author":"O. Goldreich","year":"2003","unstructured":"Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. Random Structures and Algorithms\u00a023(1), 23\u201357 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"38_CR19","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\u00a017, 70\u201393 (2008)","journal-title":"Computational Complexity"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"Naor, J., Naor, M.: Small-bias Probability Spaces: Efficient Constructions and Applications. SIAM J. on Computing\u00a022, 838\u2013856 (1993)","DOI":"10.1137\/0222053"},{"key":"38_CR21","doi-asserted-by":"crossref","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Testing Membership in Parenthesis Laguages. Random Structures and Algorithms\u00a022(1), 98\u2013138 (2003)","DOI":"10.1002\/rsa.10067"},{"key":"38_CR22","unstructured":"Pikhurko, O.: An Analytic Approach to Stability (2009), http:\/\/arxiv.org\/abs\/0812.0214"},{"key":"38_CR23","unstructured":"Ron, D.: Property testing. In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolim, J.D.P. (eds.) Handbook on Randomization, vol.\u00a0II, pp. 597\u2013649 (2001)"},{"issue":"2","key":"38_CR24","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\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"#cr-split#-38_CR25.1","doi-asserted-by":"crossref","unstructured":"Shaltiel, R.: Recent Developments in Explicit Constructions of Extractors. In: Current Trends in Theoretical Computer Science: The Challenge of the New Century. Algorithms and Complexity, vol.\u00a01, pp. 67-95. World scientific, Singapore (2004)","DOI":"10.1142\/9789812562494_0013"},{"key":"#cr-split#-38_CR25.2","unstructured":"Preliminary version in Bulletin of the EATCS, vol. 77, pp. 67-95 (2002)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:24:18Z","timestamp":1739287458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}