## Hierarchy Theorems for Testing Properties
in Size-Oblivious Query Complexity

#### Webpage for a paper by Oded Goldreich

#### Abstract

Focusing on property testing tasks that have query complexity
that is independent of the size of the tested object
(i.e., depends on the proximity parameter only),
we prove the existence of a rich hierarchy
of the corresponding complexity classes.
That is, for essentially any function $q:(0,1]\to\N$,
we prove the existence of properties for which $\epsilon$-testing
has query complexity $\Theta(q(\Theta(\epsilon)))$.
Such results are proved in three standard domains
that are often considered in property testing: generic functions,
adjacency predicates describing (dense) graphs, and
incidence functions describing bounded-degree graphs.

These results complement hierarchy theorems
of Goldreich, Krivelevich, Newman, and Rozenberg
(Computational Complexity, 2012),
which refer to the dependence of the query complexity
on the size of the tested object, and focus on the case that
the proximity parameter is set to some small positive constant.
We actually combine both flavors and get tight results
on the query complexity of testing when allowing the
query complexity to depend on both
the size of the object and the proximity parameter.

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.