zbMATH — the first resource for mathematics

Tolerant property testing and distance approximation. (English) Zbl 1100.68109
Summary: In this paper we study a generalization of standard property testing where the algorithms are required to be more tolerant with respect to objects that do not have, but are close to having, the property. Specifically, a tolerant property testing algorithm is required to accept objects that are \(\varepsilon_{1}\)-close to having a given property \(\mathcal P\) and reject objects that are \(\varepsilon_{2}\)-far from having \(\mathcal P\), for some parameters \(0 \leqslant \varepsilon_1 < \varepsilon_2 \leqslant {1}\). Another related natural extension of standard property testing that we study, is distance approximation. Here the algorithm should output an estimate \(\hat \varepsilon\) of the distance of the object to \(\mathcal P\), where this estimate is sufficiently close to the true distance of the object to \(\mathcal P\). We first formalize the notions of tolerant property testing and distance approximation and discuss the relationship between the two tasks, as well as their relationship to standard property testing. We then apply these new notions to the study of two problems: tolerant testing of clustering and distance approximation for monotonicity. We present and analyze algorithms whose query complexity is either polylogarithmic or independent of the size of the input.

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W25 Approximation algorithms
68M15 Reliability, testing and fault tolerance of networks and computer systems
Full Text: DOI
[1] N. Ailon, B. Chazelle, Information theory in property testing and monotonicity testing in higher dimensions, in: Proceedings of the Twenty-Second Annual Symposium on Theoretical Aspects of Computer Science, STACS, 2005, pp. 434-447 · Zbl 1118.68505
[2] N. Ailon, B. Chazelle, S. Comandur, D. Liu, Estimating the distance to a monotone function, in: Proceedings of the Eight International Workshop on Randomization and Computation, RANDOM, 2004, 229-236 · Zbl 1105.68420
[3] Alon, N.; Dar, S.; Parnas, M.; Ron, D., Testing of clustering, SIAM J. discrete math., 16, 3, 393-417, (2003) · Zbl 1041.68048
[4] N. Alon, A. Shapira, A characterization of the (natural) graph properties testable with one-sided error, in: Proceedings of the Forty-Sixth Annual Symposium on Foundations of Computer Science, FOCS, 2005, pp. 429-438
[5] T. Batu, F. Ergun, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, Rahul Sami, A sublinear algorithm for weakly approximating edit distance, in: Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing, STOC, 2003, pp. 316-324 · Zbl 1192.68872
[6] T. Batu, L. Fortnow, R. Rubinfeld, W. Smith, P. White, Testing that distributions are close, in: Proceedings of the Forty-First Annual Symposium on Foundations of Computer Science, FOCS, 2000, pp. 259-269
[7] Batu, T.; Rubinfeld, R.; White, P., Fast approximate PCPs for multidimensional bin-packing problems, Inform. and comput., 196, 1, 42-56, (2005) · Zbl 1062.68140
[8] Blum, M.; Luby, M.; Rubinfeld, R., Self-testing/correcting with applications to numerical problems, J. ACM, 47, 549-595, (1993) · Zbl 0795.68131
[9] M. Charikar, L. O’Callaghan, R. Panigraphy, Better streaming algorithms for clustering problems, in: Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing, STOC, 2003, pp. 30-39
[10] B. Chazelle, R. Rubinfeld, L. Trevisan, Approximating the minimum spanning tree weight in sublinear time, in: Automata, Languages and Programming: Twenty-Eighth International Colloquium, ICALP, 2001, pp. 190-200 · Zbl 0987.68527
[11] Czumaj, A.; Sohler, C., Abstract combinatorial programs and efficient property testers, SIAM J. comput., 34, 3, 580-615, (2005) · Zbl 1075.68099
[12] Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, A. Samorodnitsky, Improved testing algorithms for monotonicity, in: Proceedings of the Third International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM, 1999, pp. 97-108 · Zbl 0949.68178
[13] Ergun, F.; Kannan, S.; Kumar, S.R.; Rubinfeld, R.; Viswanathan, M., Spot-checkers, J. comput. system sci., 60, 3, 717-751, (2000) · Zbl 0961.68036
[14] Fischer, E., The art of uninformed decisions: A primer to property testing, Bull. eur. assoc. theor. comput. sci., 75, 97-126, (2001) · Zbl 1024.68045
[15] Fischer, E., On the strength of comparisons in property testing, Inform. and comput., 189, 1, 107-116, (2004) · Zbl 1090.68051
[16] E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, A. Samorodnitsky, Monotonicity testing over general poset domains, in: Proceedings of the Thirty-Fourth Annual ACM Symposium on the Theory of Computing, STOC, 2002, pp. 474-483 · Zbl 1192.68359
[17] E. Fischer, I. Newman, Testing versus estimation of graph properties, in: Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing, STOC, 2005, pp. 138-146 · Zbl 1192.68480
[18] O. Goldreich, Combinatorial property testing—a survey, in: Randomization Methods in Algorithm Design, 1998, pp. 45-60
[19] Goldreich, O.; Goldwasser, S.; Lehman, E.; Ron, D.; Samorodnitsky, A., Testing monotonicity, Combinatorica, 20, 3, 301-337, (2000) · Zbl 0964.68148
[20] Goldreich, O.; Goldwasser, S.; Ron, D., Property testing and its connection to learning and approximation, J. ACM, 45, 4, 653-750, (1998) · Zbl 1065.68575
[21] V. Guruswami, A. Rudra, Tolerant locally testable codes, in: Proceedings of the Ninth International Workshop on Randomization and Computation, RANDOM, 2005, pp. 306-317 · Zbl 1105.68347
[22] S. Halevy, E. Kushilevitz, Distribution-free property testing, in: Proceedings of the Seventh International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM, 2003, pp. 302-317 · Zbl 1279.68105
[23] S. Halevy, E. Kushilevitz, Testing monotonicity over graph products, in: Automata, Languages and Programming: Thirty-First International Colloquium, ICALP, 2004, pp. 721-732 · Zbl 1099.68681
[24] Kearns, M.J.; Schapire, R.E.; Sellie, L.M., Toward efficient agnostic learning, Machine learning, 17, 2-3, 115-141, (1994) · Zbl 0938.68797
[25] Parnas, M.; Ron, R.; Rubinfeld, R., Tolerant property testing and distance approximation, (2004), Technical Report TR04-010, Electronic Colloquium on Computational Complexity (ECCC), available from
[26] Ron, D., Property testing, (), 597-649 · Zbl 1048.68064
[27] Rubinfeld, R.; Sudan, M., Robust characterization of polynomials with applications to program testing, SIAM J. comput., 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.