Combinatorial property testing (a survey)
Oded Goldreich · DIMACS series in discrete mathematics and theoretical computer science · 1998
We consider the question of determining whether a given object has a predetermined property or is "far" from any object having the property. Specifically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. We consider (randomized) algorithms which may query the function at arguments of their choice, and seek algorithms which query the function at relatively few places. We focus on combinatorial properties, and specifically on graph properties. The two standard representations of graphs -- by adjacency matrices and by incidence lists -- yield two different models for testing graph properties. In the first model, most appropriate for dense graphs, distance between N-vertex graphs is measured as the fraction of edges on which the graphs disagree over N 2 . In the second model, most appropriate for bounded-degree graphs, distance between N-vertex d-degree graphs is measured as the fraction of edges on ...