{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,27]],"date-time":"2025-02-27T05:24:00Z","timestamp":1740633840679,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642163661"},{"type":"electronic","value":"9783642163678"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_22","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"289-294","source":"Crossref","is-referenced-by-count":0,"title":["Hierarchy Theorems for Property Testing"],"prefix":"10.1007","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","reference":[{"key":"22_CR1","doi-asserted-by":"publisher","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.\u00a0of Algorithms"},{"key":"22_CR2","doi-asserted-by":"publisher","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"},{"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)","key":"22_CR3","DOI":"10.1145\/1132516.1132555"},{"issue":"3","key":"22_CR4","doi-asserted-by":"publisher","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":"22_CR5","doi-asserted-by":"publisher","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"},{"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)","key":"22_CR6","DOI":"10.1145\/1374376.1374433"},{"issue":"3","key":"22_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":"22_CR8","doi-asserted-by":"publisher","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"},{"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)","key":"22_CR9","DOI":"10.1109\/SFCS.2002.1181886"},{"issue":"3","key":"22_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"},{"doi-asserted-by":"crossref","unstructured":"Fischer, E., Matsliah, A.: Testing Graph Isomorphism. In: 17th SODA, pp. 299\u2013308 (2006)","key":"22_CR11","DOI":"10.1145\/1109557.1109591"},{"issue":"3","key":"22_CR12","doi-asserted-by":"publisher","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":"Combinatorica"},{"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)","key":"22_CR13","DOI":"10.1145\/285055.285060"},{"issue":"2","key":"22_CR14","doi-asserted-by":"publisher","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":"22_CR15","doi-asserted-by":"publisher","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":"22_CR16","doi-asserted-by":"publisher","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":"22_CR17","doi-asserted-by":"publisher","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":"22_CR18","doi-asserted-by":"publisher","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\u00a022, 838\u2013856 (1993)","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"22_CR19","doi-asserted-by":"publisher","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\u00a022(1), 98\u2013138 (2003)","journal-title":"Random Structures and Algorithms"},{"unstructured":"Pikhurko, O.: An Analytic Approach to Stability (2009) (manuscript), http:\/\/arxiv.org\/abs\/0812.0214","key":"22_CR20"},{"issue":"3","key":"22_CR21","doi-asserted-by":"publisher","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\u00a01(3), 307\u2013402 (2008)","journal-title":"Foundations and Trends in Machine Learning"},{"issue":"2","key":"22_CR22","first-page":"73","volume":"5","author":"D. Ron","year":"2010","unstructured":"Ron, D.: Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in TCS\u00a05(2), 73\u2013205 (2010)","journal-title":"Foundations and Trends in TCS"},{"issue":"2","key":"22_CR23","doi-asserted-by":"publisher","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":"22_CR24","series-title":"Algorithms and Complexity","volume-title":"Current Trends in Theoretical Computer Science: The Challenge of the New Century","author":"R. Shaltiel","year":"2004","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, World Scientific, Singapore (2004); Preliminary version in Bulletin of the EATCS 77, 67\u201395 (2002)"}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T13:17:34Z","timestamp":1740575854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}