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 initiated the systematic study of property testing, while focusing 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 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) lower bound 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, D. Ron and A. Samorodnitsky, Testing Monotinicity, 1998 (improved 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. (See also the errata.)
  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. Such basic tests are called POTs.
• 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.
  This work shows that cycles in N-vertex graphs that have 1.01N edges can be found in $tildeO(sqrt(N)$-time, whereas tree structures can be found in constant-time if the graph is 0.01-far from lacking them. These sublinear time algorithms are closely related to one-sided error property testers.
• O. Goldreich, On Testing Computability by Small Width OBDDs, April 2010.
  The lower bounds are mostly superseded by Blais, Brody, and Matulef's work Property Testing Lower Bounds Via Communication Complexity.
• O. Goldreich, On the Effect of the Proximity Parameter on Property Testers, Feb. 2012.
• O. Goldreich and I. Shinkar, Two-Sided Error Proximity Oblivious Testing, Mar. 2012.
• O. Goldreich, On Multiple Input Problems in Property Testing, May 2013.
• O. Goldreich, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, May 2013.