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



REPORTS > DETAIL:

Paper:

TR06-089 | 16th July 2006 00:00

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

RSS-Feed

Abstract:

We show that in the bounded degree model for graph property testing,
adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We show that every tester for a non-trivial property that makes o(\sqrt n / d) queries to the input graph on n vertices of degree at most d has to be adaptive.



ISSN 1433-8092 | Imprint