Combinatorial Property Testing: Surveys and Works

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. Typically, 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 own surveys, provided below. For a wider perspective, see Dana Ron's tutorials (below).

Surveys

• O. Goldreich, A Brief Introduction to Property Testing, 2010.
• O. Goldreich, Introduction to Testing Graph Properties, 2010.
  The aim of this article is to introduce the reader to the study of testing graph properties, while focusing on the main models and issues involved. It superseeds the following prior two surveys
  • O. Goldreich, Combinatorial Property Testing -- A Survey (1997)
  • O. Goldreich, Property Testing in Massive Graphs (1999)
  as well as contemplations on testing graph properties (2005).
• O. Goldreich, Relaxing the Requirements: Approximation - the case of Decision or Property Testing.
  This brief overview of the area appeared as Sec. 10.1.2 of Computational Complexity: A Conceptual Perspective (2008).
• D. Ron, three tutorials. The two later tutorials provide different perspectives (and superseed the earlier one).
  • Property Testing (A Tutorial), 2000.
  • Property Testing: A Learning Theory Perspective, 2008.
  • Algorithmic and Analysis Techniques in Property Testing, 2009.

• 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.
• A collection of surveys and extended abstracts in property testing, edited by Oded Goldreich, 2010.

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 initiates the study of testing graph properties in the incidence list representation. The highlights include testers for connectivity, k-edge-connectivity, and cycle-freeness as well as a sqrt(N) for bipartite testing.
• 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.
  See 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.
• L. Avigad and O. Goldreich, Testing Graph Blow-Up, March 2010.
  This work proves that graph blow-up properties can be tested non-adaptively in $tildeO(1/\eps)$ queries.
• O. Goldreich and T. Kaufman, Proximity Oblivious Testing and the Role of Invariances, April 2010.
• A. Czumaj, O. Goldreich, D. Ron, C. Seshadhri, A. Shapira, and C. Sohler, Finding Cycles and Trees in Sublinear Time, April 2010.
• O. Goldreich, On Testing Computability by Small Width OBDDs, April 2010.