{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T15:20:30Z","timestamp":1726154430761},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407706"},{"type":"electronic","value":"9783540451983"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_31","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:32:30Z","timestamp":1294439550000},"page":"370-381","source":"Crossref","is-referenced-by-count":12,"title":["Approximate Testing of Visual Properties"],"prefix":"10.1007","author":[{"given":"Sofya","family":"Raskhodnikova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Batu, T., Ergun, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., Sami, R.: A Sublinear Algorithm for Weakly Approximating Edit Distance. In: Proceedings of the 35th ACM STOC (2003)","DOI":"10.1145\/780542.780590"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: 3CNF Properties are Hard to Test. In: Proceedings of the 35th ACM STOC (2003)","DOI":"10.1145\/780542.780594"},{"issue":"4","key":"31_CR3","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.: Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for computing machinery\u00a036(4), 929\u2013965 (1989)","journal-title":"Journal of the Association for computing machinery"},{"key":"31_CR4","unstructured":"Bogdanov, A., Obata, K., Trevisan, L.: A linear lower bound on the query complexity of property testing algorithms for 3-coloring in bounded-degree graphs. In: Proceedings of the 42nd IEEE FOCS (2002)"},{"key":"31_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/3-540-48224-5_16","volume-title":"Automata, Languages and Programming","author":"B. Chazelle","year":"2001","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, p. 190. Springer, Heidelberg (2001)"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Property testing with geometric queries. In: Proceedings of the 9th European Symposium on Algorithms, pp. 266\u2013277 (2001)","DOI":"10.1007\/3-540-44676-1_22"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C., Ziegler, M.: Property testing in computational geometry. In: Proceedings of the 8th European Symposium on Algorithms, pp. 155\u2013166 (2000)","DOI":"10.1007\/3-540-45253-2_15"},{"issue":"3","key":"31_CR8","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0890-5401(89)90002-3","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D., Kearns, M., Valiant, L.: General Lower Bound on the Number of Examples Needed for Learning. Information and Computation\u00a082(3), 247\u2013261 (1989)","journal-title":"Information and Computation"},{"key":"31_CR9","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science\u00a075, 97\u2013126 (2001)","journal-title":"The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science"},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"Fischer, E., Newman, I.: Testing of matrix properties. In: Proceedings of the 33rd ACM STOC, pp. 286-295 (2001)","DOI":"10.1145\/380752.380812"},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045, 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. In: Proceedings of the 28th ACM STOC (1997)","DOI":"10.1145\/258533.258627"},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Roth, D.: On Learning Visual Concepts and DNF Formulae. Machine Learning (1996)","DOI":"10.1007\/BF00117833"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Maass, W., Turan, G.: On the complexity of learning from counterexamples. In: Proceedings of the 30th IEEE FOCS, pp. 262\u2013267 (1989)","DOI":"10.1109\/SFCS.1989.63488"},{"key":"31_CR15","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing (a tutorial). In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolimeds, J.D.P. (eds.) Handbook of Randomized Computing, Kluwer Press, Dordrecht (2001)"},{"key":"31_CR16","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 of Computing\u00a025, 252\u2013271 (1996)","journal-title":"SIAM Journal of Computing"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"Valiant, L.: A theory of the learnable. Communications of the ACM\u00a027, 1134\u20131142 (1984)","journal-title":"Communications of the ACM"}],"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-540-45198-3_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T14:05:16Z","timestamp":1559916316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}