zbMATH — the first resource for mathematics

Contemplations on testing graph properties. (English) Zbl 1291.05195
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, 547-554 (2011).
Summary: This article documents two programmatic comments regarding testing graph properties, which I made during the Dagstuhl workshop on Sublinear-Time Algorithms (July 2005). The first comment advocates paying more attention to the dependence of the tester’s complexity on the proximity parameter. The second comment advocates paying more attention to the question of testing general graphs (rather than dense or bounded-degree ones). In addition, this article includes a suggestion to view and discuss property testing within the framework of promise problems.
For the entire collection see [Zbl 1220.68005].

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68W20 Randomized algorithms
Full Text: DOI
[1] Alon, N.: Testing subgraphs of large graphs. Random Structures and Algorithms 21, 359–370 (2002) · Zbl 1027.68095
[2] Alon, N.V., Fischer, E.V., Krivelevich, M.V., Szegedy, M.V.: Efficient Testing of Large Graphs. Combinatorica 20, 451–476 (2000) · Zbl 1052.68096
[3] Alon, N.V., Fischer, E.V., 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
[4] Alon, N.V., Krivelevich, M.V.: Testing k-Colorability. SIAM Journal on Disc. Math. 15(2), 211–227 (2002) · Zbl 1001.05058
[5] Alon, N., Shapira, A.: Every Monotone Graph Property is Testable. In: 37th STOC, pp. 128–137 (2005) · Zbl 1192.68466
[6] Alon, N., Shapira, A.: A Characterization of the (natural) Graph Properties Testable with One-Sided. In: 46th FOCS (2005) (to appear) · Zbl 1152.05055
[7] Alon, N., Shapira, A.: A Separation Theorem in Property Testing (2004) (unpublished manuscript)
[8] Bender, M.V., Ron, D.V.: Testing acyclicity of directed graphs in sublinear time. Random Structures and Algorithms, 184–205 (2002) · Zbl 1002.68113
[9] Bogdanov, A., Obata, K., Trevisan, L.: A lower bound for testing 3-colorability in bounded-degree graphs. In: 43rd FOCS, pp. 93–102 (2002)
[10] Bogdanov, A., Trevisan, L.: Lower Bounds for Testing Bipartiteness in Dense Graphs. In: IEEE Conference on Computational Complexity, pp. 75–81 (2004)
[11] Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. In: Yu, Y., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 190–200. Springer, Heidelberg (2001) · Zbl 0987.68527
[12] Even, S., Selman, A.L., Yacobi, Y.: The Complexity of Promise Problems with Applications to Public-Key Cryptography. Inform. and Control 61, 159–173 (1984) · Zbl 0592.94012
[13] Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science 75, 97–126 (2001) · Zbl 1024.68045
[14] Fischer, E., Newman, I.: Testing versus estimation of graph properties. In: 37th STOC, pp. 138–146 (2005) · Zbl 1192.68480
[15] Goldreich, O.: Introduction to Testing Graph Properties. In: Goldreich, O., et al.: Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 549–556. Springer, Heidelberg (2011) · Zbl 1343.68299
[16] Goldreich, O.: On Promise Problems. In: memory of Shimon Even (1935–2004). ECCC, TR05-018 (January 2005)
[17] Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM, 653–750 (July 1998) · Zbl 1065.68575
[18] Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica, 302–343 (2002) · Zbl 0990.68103
[19] Goldreich, O., Ron, D.: A sublinear bipartite tester for bounded degree graphs. Combinatorica 19(3), 335–373 (1999) · Zbl 0932.68053
[20] Goldreich, O., Ron, D.: On Testing Expansion in Bounded-Degree Graphs. In: ECCC, TR00-020 (March 2000)
[21] Goldreich, O., Ron, D.: Approximating Average Parameters of Graphs. In: ECCC, TR05-073 (July 2005)
[22] Goldreich, O., Ron, D.: Algorithmic Aspects of Property Testing in the Dense Graphs Model. In: ECCC, TR08-039 (2008)
[23] Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. Random Structures and Algorithms 23(1), 23–57 (2003) · Zbl 1048.68062
[24] Gonen, M., Ron, D.: On the Benefits of Adaptivity in Property Testing of Dense Graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol. 4627, pp. 525–539. Springer, Heidelberg (2007) · Zbl 1171.68696
[25] Hochbaum, D. (ed.): Approximation Algorithms for NP-Hard Problems. PWS (1996) · Zbl 1368.68010
[26] Kaufman, T., Krivelevich, M., Ron, D.: Tight Bounds for Testing Bipartiteness in General Graphs. SIAM Journal on Computing 33(6), 1441–1483 (2004) · Zbl 1101.68607
[27] Parnas, M., Ron, D.: Testing the diameter of graphs. Random Structures and Algorithms 20(2), 165–183 (2002) · Zbl 1052.68104
[28] Ron, D.: Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in TCS 5(2), 73–205 (2010) · Zbl 1184.68610
[29] 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.