ECCC-Report TR06-089https://eccc.weizmann.ac.il/report/2006/089Comments and Revisions published for TR06-089en-usSat, 29 Jul 2006 20:04:18 +0300
Paper TR06-089
| A Note on Adaptivity in Testing Properties of Bounded Degree Graphs |
Sofya Raskhodnikova,
Adam Smith
https://eccc.weizmann.ac.il/report/2006/089We 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.
Sat, 29 Jul 2006 20:04:18 +0300https://eccc.weizmann.ac.il/report/2006/089