zbMATH — the first resource for mathematics

A brief introduction to property testing. (English) Zbl 1343.68298
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 465-469 (2011).
Summary: This short article provides a brief description of the main issues that underly the study of property testing.
For the entire collection see [Zbl 1220.68005].

68W20 Randomized algorithms
Full Text: DOI
[1] Alon, N., Fischer, E., Newman, I., Shapira, A.: A Combinatorial Characterization of the Testable Graph Properties: It’s All About Regularity. In: 38th STOC, pp. 251–260 (2006) · Zbl 1301.05354
[2] Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that Distributions are Close. In: 41st FOCS, pp. 259–269 (2000)
[3] Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. JCSS 47(3), 549–595 (1990); Extended abstract in 22nd STOC (1990) · Zbl 0795.68131
[4] Goldreich, O. (ed.): Property Testing. LNCS, vol. 6390, pp. 142–157. Springer, Heidelberg (2010) · Zbl 1309.68227
[5] Goldreich, O.: Introduction to Testing Graph Properties. In: Goldreich, O., et al.: Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 467–471. Springer, Heidelberg (2011) · Zbl 1343.68299
[6] Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM, 653–750 (July 1998); Extended abstract in 37th FOCS (1996) · Zbl 1065.68575
[7] Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. Algorithmica 32(2), 302–343 (2002); Extended abstract in 29th STOC (1997) · Zbl 0990.68103
[8] Goldreich, O., Ron, D.: A Sublinear Bipartitness Tester for Bounded Degree Graphs. Combinatorica 19(3), 335–373 (1999); Extended abstract in 30th STOC (1998) · Zbl 0932.68053
[9] Kaufman, T., Krivelevich, M., Ron, D.: Tight bounds for testing bipartiteness in general graphs. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. RANDOM, pp. 341–353. Springer, Heidelberg (2003) · Zbl 1279.05068
[10] Parnas, M., Ron, D., Rubinfeld, R.: Tolerant Property Testing and Distance Approximation. JCSS 72(6), 1012–1042 (2006); Preliminary version in ECCC (2004) · Zbl 1100.68109
[11] Ron, D.: Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning 1(3), 307–402 (2008)
[12] Ron, D.: Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in TCS 5(2), 73–205 (2010) · Zbl 1184.68610
[13] Rubinfeld, R., Sudan, M.: Robust Characterization of Polynomials with Applications to Program Testing. SIAM Journal on Computing 25(2), 252–271 (1996) · Zbl 0844.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.