Combinatorial Property Testing

Oded Goldreich

Property Testing is concerned with approximate decisions, where the task is distinguishing between objects having a predetermined property and objects that are ``far'' from having this 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 that may query the function at arguments of their choice, and seek algorithms of very low complexity (i.e., much lower than the size of the function's domain).

Most of the works mentioned below focus on combinatorial properties, and specifically on graph properties. The two standard representations of graphs - by adjacency matrix and by incidence lists - yield two different models for testing graph properties. In the first model graphs, 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 graphs, most appropriate for bounded-degree graphs, distance between N-vertex d-degree graphs is measured as the fraction of edges on which the graphs disagree over dN. These two models are the topic of my two surveys, provided below. For a wider perspective, see Dana Ron's tutorial (below).

Surveys

• O. Goldreich, Combinatorial Property Testing -- A Survey, 1997.
• O. Goldreich, Property Testing in Massive Graphs, 1999.
• D. Ron, Property Testing (A Tutorial), 2000.
• O. Goldreich, Relaxing the Requirements: Approximation - the case of Decision or Property Testing (Sec. 10.1.2), extract of Computational Complexity: A Conceptual Perspective (2008).
• D. Ron, Property Testing: A Learning Theory Perspective, 2008.
• D. Ron, Algorithmic and Analysis Techniques in Property Testing, 2009.

For a wider perspective and more details, see

• An extensive bibliography of Property Testing and related areas compiled (in 2004) by Bernard Chazelle.
  (See local copy.)
• lecture notes on sublinear algorithms by Dana Ron.

My own papers in the area (in chronological order)

• O. Goldreich, S. Goldwasser and D. Ron, Property Testing and its connection to Learning and Approximation, 1996.
  This work presents the general model, and focuses on testing graph properties in the adjecency matrix representation. The highlights include testers for various graph partition problems (e.g., k-colorability, rho-clique, etc) as well as a generic treatment of any such problem.
• O. Goldreich and D. Ron, Property Testing in Bounded-Degree Graphs, 1997. (see revision, 1999).
  This work focuses on testing graph properties in the incidence list representation.
• O. Goldreich and D. Ron, A Sublinear Bipartite Tester for Bounded Degree Graphs, 1997.
  This work presents a Bipartite Tester of complexity approximately sqrt(N) in the incidence list representation.
• O. Goldreich, S. Goldwasser, E. Lehman and D. Ron, Testing Monotinicity, 1998.
  Revised and improved version with Alex Samorodnitsky, 1999.
• Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky, Improved Testing Algorithms for Monotonicity, 1999.
• O. Goldreich and D. Ron, On Testing Expansion in Bounded-Degree Graphs, March 2000.
• O. Goldreich and L. Trevisan, Three Theorems regarding Testing Graph Properties, 2001.
  The first theorem asserts the existence of monotone graph properties that are extremely hard to test, the second theorem asserts that canonical testers suffice for the model, and the third theorem differntiates one-sided and two-sided error testing within the setting of generalized graph partition problems.
• O. Goldreich and O. Sheffet, On the randomness complexity of property testing, Feb. 2007.
• O. Goldreich, On the Average-Case Complexity of Property Testing, July 2007.
• O. Goldreich and D. Ron, Algorithmic Aspects of Property Testing in the Dense Graphs Model, April 2008.
  This work initiates a refined study of the query complexity of testing in this model, and focuses on the relation between adaptive and non-adaptive testers.
• O. Goldreich and D. Ron, On Proximity Oblivious Testing, April 2008.
  This work defines and studies a restricted class of testers; specifically, testers that repeatedly invoke a basic test that is not given the proximity parameter as input.
• O. Goldreich, M. Krivelevich, I. Newman and E. Rozenberg, Hierarchy Theorems for Property Testing, Nov. 2008.