Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-089 | 16th July 2006 00:00

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs



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