Article PDF
Avoid common mistakes on your manuscript.
References
N. Alon: Testing subgraphs in large graphs, in: Proc. 42nd IEEE FOCS, IEEE (2001), pp. 434–441; also: Random Structures and Algorithms 21 (2002), 359–370.
N. Alon, E. Fischer, M. Krivelevich and M. Szegedy: Efficient testing of large graphs, in: Proc. of 40th FOCS, New York, NY, IEEE (1999), pp. 656–666; also: Combinatorica 20(3) (2000), 451–476.
N. Alon, E. Fischer, I. Newman and A. Shapira: A combinatorial characterization of the testable graph properties: it’s all about regularity; in: Proc. of STOC 2006, pp. 251–260; also: SIAM Journal on Computing, to appear.
N. Alon and A. Shapira: Every monotone graph property is testable, in: Proc. of STOC 2005, pp. 128–137; also: SIAM Journal on Computing, to appear.
N. Alon and A. Shapira: A characterization of the (natural) graph properties testable with one-sided error, SIAM J. on Computing 37(6) (2008), 1703–1727.
N. Alon and J. H. Spencer: The Probabilistic Method, Second Edition, Wiley, New York, 2000.
M. Blum, M. Luby and R. Rubinfeld: Self-testing/correcting with applications to numerical problems, JCSS 47 (1993), 549–595.
P. Erdős: Graph theory and probability, Canad. J. Mathematics 11 (1959), 34–38.
P. Erdős: On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183–190.
E. Fischer: 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 75 (2001), 97–126.
O. Goldreich: Combinatorial property testing — a survey, in: Randomization Methods in Algorithm Design (P. Pardalos, S. Rajasekaran and J. Rolim eds.), AMSDIMACS (1998), pp. 45–60.
O. Goldreich, S. Goldwasser and D. Ron: Property testing and its connection to learning and approximation, JACM 45(4) (1998), 653–750.
O. Goldreich and D. Ron: Property Testing in Bounded-Degree Graphs, in: Proc. of STOC (1997), pp. 406–415.
O. Goldreich and L. Trevisan: Three theorems regarding testing graph properties, Random Structures and Algorithms 23(1) (2003), 23–57.
T. Kaufman, M. Krivelevich and D. Ron: Tight bounds for testing bipartiteness in general graphs, SIAM J. on Computing 33 (2004), 1441–1483.
T. Kővári, V. T. Sós and P. Turán: On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50–57.
L. Lovász and B. Szegedy: Graph limits and testing hereditary graph properties, Technical Report MSR-TR-2005-110, Microsoft Research.
A. Lubotzky, R. Phillips and P. Sarnak: Ramanujan graphs, Combinatorica 8(3) (1988), 261–277.
C. Papadimitriou: Computational Complexity, Addison Wesley, 1994.
M. Parnas and D. Ron: Testing the diameter of graphs, Random structures and algorithms 20 (2002), 165–183.
D. Ron: Property testing, in: P. M. Pardalos, S. Rajasekaran, J. Reif and J. D. P. Rolim, editors, Handbook of Randomized Computing, Vol. II, Kluwer Academic Publishers, 2001, pp. 597–649.
R. Rubinfeld and M. Sudan: Robust characterization of polynomials with applications to program testing, SIAM J. on Computing 25 (1996), 252–271.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.
This work forms part of the author’s Ph.D. thesis. Research supported by a Charles Clore Foundation Fellowship and by an IBM Ph.D. Fellowship.