Hierarchy Theorems for Property Testing
Webpage for a paper by Goldreich, Krivelevich, Newman and Rozenberg
Abstract
Referring to the query complexity of property testing,
we prove the existence of a rich hierarchy of corresponding
complexity classes. That is, for any relevant function $q$,
we prove the existence of properties that have testing
complexity Theta(q).
Such results are proven in three standard
domains often considered in property testing: generic functions,
adjacency predicates describing (dense) graphs, and
incidence functions describing bounded-degree graphs.
While in two cases the proofs are quite straightforward,
the techniques employed in the case of the dense graph model
seem significantly more involved.
Specifically, problems that arise and are treated in the latter case
include (1) the preservation of distances between graph
under a blow-up operation, and (2) the construction
of monotone graph properties that have local structure.
Material available on-line
- First version posted:
Nov. 2008.
- 1st revision: adding a one-sided error hierarchy theorem,
Dec. 2008.
- 2nd revision: correcting a confusion/error in Section 6,
Mar. 2009.
- 3nd revision: detailing some arguments, re-organizing,
and updating the conclusions,
Nov. 2009.
- 4th revision:
Sept. 2010
[PDF].
- Eyal Rozenberg's
PhD
Thesis, which contains a version of this work as its Chapter 4.
This version is most updated and corrects some inaccuracies that,
unfortunately, appear in the 4th version of the paper.
Back to
either Oded Goldreich's homepage.
or general list of papers.