## Testing Graphs in Vertex-Distribution-Free Models

#### Webpage for a paper by Oded Goldreich

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

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.