Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-171 | 8th March 2019 15:59

Testing Graphs in Vertex-Distribution-Free Models

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 8th March 2019 15:59
Downloads: 717
Keywords: 


Abstract:

Prior 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.



Changes to previous version:

Various minor corrections including correcting Thm 3.8; correcting/augmenting the proofs of Thm 2.8 (see Clm 2.8.1), Thm 2.13 and Thm 4.5.

Revising Sec 5.1 in light of a subsequent work of Gishboliner and Shapira (to appear in STOC'19).

Numerous improvements in the presentation.


Paper:

TR18-171 | 10th October 2018 16:02

Testing Graphs in Vertex-Distribution-Free Models





TR18-171
Authors: Oded Goldreich
Publication: 10th October 2018 16:02
Downloads: 783
Keywords: 


Abstract:

Prior 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.



ISSN 1433-8092 | Imprint