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