ECCC-Report TR18-171https://eccc.weizmann.ac.il/report/2018/171Comments and Revisions published for TR18-171en-usFri, 08 Mar 2019 15:59:22 +0200
Revision 1
| Testing Graphs in Vertex-Distribution-Free Models |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2018/171#revision1Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries).
Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution (and, in addition, obtain answers to the usual graph-queries).
We initiate a study of testing graph properties in such settings, while adapting the definition of distance between graphs so that it reflects the different probability weight of different vertices.
Hence, the distance to the property represents the relative importance of the ``part of the graph'' that violates the property.
We consider such ``vertex-distribution free'' (VDF) versions of the two most-studied models of testing graph properties (i.e., the dense graph model and the bounded-degree model).
In both cases, we show that VDF testing within complexity that is independent of the size of the tested graph is possible only if the same property can be tested in the standard model with one-sided error and size-independent complexity.
We also show that this necessary condition is not sufficient; yet, we present size-independent VDF testers for many of the natural properties that satisfy the necessary condition.
Fri, 08 Mar 2019 15:59:22 +0200https://eccc.weizmann.ac.il/report/2018/171#revision1
Paper TR18-171
| Testing Graphs in Vertex-Distribution-Free Models |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2018/171Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries).
Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution (and, in addition, obtain answers to the usual graph-queries).
We initiate a study of testing graph properties in such settings, while adapting the definition of distance between graphs so that it reflects the different probability weight of different vertices.
Hence, the distance to the property represents the relative importance of the ``part of the graph'' that violates the property.
We consider such ``vertex-distribution free'' (VDF) versions of the two most-studied models of testing graph properties (i.e., the dense graph model and the bounded-degree model).
In both cases, we show that VDF testing within complexity that is independent of the size of the tested graph is possible only if the same property can be tested in the standard model with one-sided error and size-independent complexity.
We also show that this necessary condition is not sufficient; yet, we present size-independent VDF testers for many of the natural properties that satisfy the necessary condition.
Wed, 10 Oct 2018 16:02:31 +0300https://eccc.weizmann.ac.il/report/2018/171