Revision #1 Authors: Oded Goldreich, Michael Krivelevich, Ilan Newman and Eyal Rozenberg

Accepted on: 4th January 2009 00:00

Downloads: 2574

Keywords:

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.)

TR08-097 Authors: Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Publication: 14th November 2008 15:56

Downloads: 2172

Keywords:

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.