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



REPORTS > KEYWORD > MONOTONE GRAPH PROPERTIES:
Reports tagged with Monotone Graph Properties:
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