ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > EYAL ROZENBERG:
All reports by Author Eyal Rozenberg:

TR08-097 | 14th November 2008
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Hierarchy Theorems for Property Testing

Revisions: 1
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 >>>



ISSN 1433-8092 | Imprint