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
For a wider perspective and more details, see
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.