ECCC-Report TR08-097https://eccc.weizmann.ac.il/report/2008/097Comments and Revisions published for TR08-097en-usSun, 04 Jan 2009 00:00:00 +0200
Revision 1
| Hierarchy Theorems for Property Testing Revision of: TR08-097 |
Oded Goldreich,
Michael Krivelevich,
Ilan Newman
and Eyal Rozenberg
https://eccc.weizmann.ac.il/report/2008/097#revision1
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.
(This revision includes a new hierarchy theorem for one-sided testing
[see Sec 6], which resolves an open problem post in the first version.)
Sun, 04 Jan 2009 00:00:00 +0200https://eccc.weizmann.ac.il/report/2008/097#revision1
Paper TR08-097
| Hierarchy Theorems for Property Testing |
Oded Goldreich,
Michael Krivelevich,
Ilan Newman,
Eyal Rozenberg
https://eccc.weizmann.ac.il/report/2008/097Referring 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.
Fri, 14 Nov 2008 15:56:36 +0200https://eccc.weizmann.ac.il/report/2008/097