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 my book Introduction to Property Testing and 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. (Link broken...)
- Property Testing: A Learning Theory Perspective, 2008.
- Algorithmic and Analysis Techniques in Property Testing, 2009.

For a wider perspective and more details, see

Introduction to Property Testing

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.

See also a survey of the related topic of Short Locally Testable Codes and Proofs (by Oded Goldreich, 2004 and 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 [revised 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).
The focus is on testing monotonicity of Boolean functions on the hypercube, but generalizations are studied too.
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.
O. Goldreich, The uniform distribution is complete with respect to testing identity to a fixed distribution, Feb. 2016.
O. Goldreich, Reducing testing affine spaces to testing linearity, May 2016.
O. Goldreich and D. Ron, On Sample-Based Testers, Aug. 2013.
This work initiates a systematic study of a model of property testing that was neglected so far, providing several general positive results as well as by revealing relations between variants of this model.
O. Goldreich and D. Ron, On Learning and Testing Dynamic Environments, Mar. 2014.
This work initiates the study of testing and learning environments that evolve according to a local rule; it presents both general results about the model and specific results that refer to two natural cases.
O. Goldreich, T. Gur, and I. Komargodski, Strong Locally Testable Codes with Relaxed Local Decoders, Feb. 2014.
O. Goldreich, T. Gur, and R. Rothblum, Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs, Feb. 2015.
O. Goldreich and D. Ron, The Subgraph Testing Model, Mar. 2018.
This work initiates a study of testing properties of subgraphs of a fixed (or an explicitly given) graph; that is, the tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.
I. Dinur, O. Goldreich, and T. Gur, Every set in P is strongly testable under a suitable encoding, Mar 2018.
O. Goldreich, Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity, May 2018.
O. Goldreich, Flexible models for testing graph properties, May 2018.
O. Goldreich, Testing Graphs in Vertex-Distribution-Free Models , Oct. 2018.
This work initiates a study of graph properties in a setting in which the tester only obtains random vertices drawn according to an arbitrary distribution (and, in addition, obtains answers to the usual graph-queries), when adapting the definition of distance between graphs so that it reflects the different probability weight of different vertices.
O. Goldreich, Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model, May 2019.
O. Goldreich, On the Complexity of Estimating the Effective Support Size, June 2019.
O. Goldreich, Testing Isomorphism in the Bounded-Degree Graph Model, August 2019.
O. Goldreich, On Testing Hamiltonicity in the Bounded Degree Graph Model, July 2020.
O. Goldreich, On Testing Asymmetry in the Bounded Degree Graph Model, August 2020.
O. Goldreich and A. Wigderson, Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing, Sept 2020.
O. Goldreich and A. Wigderson, Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model, Nov 2020.
O. Goldreich, Robust Self-Ordering versus Local Self-Ordering, March 2021.
O. Goldreich and D. Ron, A Lower Bound on the Complexity of Testing Grained Distributions, September 2021.
O. Goldreich and D. Ron, Testing Distributions of Huge Objects, September 2021.
N. Bshouty and O. Goldreich, On properties that are non-trivial to test, Feb 2022.
O. Goldreich and L. Tauber, Testing in the bounded-degree graph model with degree bound two, Dec 2022.

Back to Oded Goldreich's homepage or to the full list of papers.