Hierarchy Theorems for Property Testing |
| |
Authors: | Oded Goldreich Michael Krivelevich Ilan Newman Eyal Rozenberg |
| |
Affiliation: | 1. Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel 2. School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel 3. Department of Computer Science, Haifa University, Haifa, Israel 4. Department of Computer Science, Technion, Haifa, Israel
|
| |
Abstract: | 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 Θ(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, and 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|