{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:25:56Z","timestamp":1787509556558,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642229343","type":"print"},{"value":"9783642229350","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_49","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T05:20:39Z","timestamp":1313126439000},"page":"579-592","source":"Crossref","is-referenced-by-count":3,"title":["Proximity Oblivious Testing and the Role of Invariances"],"prefix":"10.1007","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tali","family":"Kaufman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"49_CR1","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"},{"key":"49_CR2","doi-asserted-by":"publisher","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\u00a015, 791\u2013805 (2006)","journal-title":"Combinatorics Probability and Computing"},{"issue":"3","key":"49_CR3","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and non-approximability \u2013 towards tight results. SIAM Journal on Computing\u00a027(3), 804\u2013915 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"49_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Maatouk, G., Shpilka, A., Sudan, M.: Symmetric LDPC codes are not necessarily locally testable. ECCC, TR10-199 (2010)","DOI":"10.1109\/CCC.2011.14"},{"issue":"3","key":"49_CR5","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"},{"key":"49_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/978-3-540-85363-3_32","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Fischer","year":"2008","unstructured":"Fischer, E., Lachish, O., Matsliah, A., Newman, I., Yahalom, O.: On the Query Complexity of Testing Orientations for Being Eulerian. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 402\u2013415. Springer, Heidelberg (2008) Full version available from, http:\/\/www.cs.technion.ac.il\/~oyahalom"},{"key":"49_CR7","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":"49_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-22670-0","volume-title":"Studies in Complexity and Cryptography","author":"O. Goldreich","year":"2011","unstructured":"Goldreich, O., Kaufman, T.: Proximity Oblivious Testing and the Role of Invariances. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. LNCS, vol.\u00a06650, pp. 1\u20135. Springer, Heidelberg (2011)"},{"issue":"2","key":"49_CR9","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"},{"key":"#cr-split#-49_CR10.1","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: On Proximity Oblivious Testing. ECCC, TR08-041 (2008);","DOI":"10.1145\/1536414.1536436"},{"key":"#cr-split#-49_CR10.2","unstructured":"Also in the Proceedings of the 41st STOC 2009"},{"issue":"1","key":"49_CR11","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":"49_CR12","doi-asserted-by":"crossref","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: 2-Transitivity is Insufficient for Local Testability. In: 23rd CCC, pp. 259\u2013267 (2008)","DOI":"10.1109\/CCC.2008.31"},{"key":"49_CR13","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Sudan, M.: Sparse Random Linear Codes are Locally Testable and Decodable. In: The Proceedings of the 48th FOCS, pp. 590\u2013600 (2007)","DOI":"10.1109\/FOCS.2007.8"},{"key":"49_CR14","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Sudan, M.: Algebraic Property Testing: The Role of Invariances. In: 40th STOC, pp. 403\u2013412 (2008)","DOI":"10.1145\/1374376.1374434"},{"issue":"1","key":"49_CR15","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M. Parnas","year":"2002","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic boolean formulae. SIAM Journal on Discrete Math.\u00a016(1), 20\u201346 (2002)","journal-title":"SIAM Journal on Discrete Math."},{"issue":"3","key":"49_CR16","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"},{"key":"49_CR17","unstructured":"Ron, D.: Algorithmic and Analysis Techniques in Property Testing. In: Foundations and Trends in TCS (to appear)"},{"issue":"2","key":"49_CR18","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":"49_CR19","doi-asserted-by":"crossref","unstructured":"Sudan, M.: Invariance in Property Testing. ECCC, TR10-051 (2010)","DOI":"10.1007\/978-3-642-16367-8_12"},{"key":"49_CR20","unstructured":"Sudan, M.: Testing Linear Properties: Some General Themes. ECCC, TR11-005 (2011)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22935-0_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T14:00:34Z","timestamp":1686232834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}