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-104 | 10th June 2018 18:12

Flexible models for testing graph properties

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 10th June 2018 18:12
Downloads: 586
Keywords: 


Abstract:

The standard models of testing graph properties postulate that the vertex-set consists of $\{1,2,...,n\}$, where $n$ is a natural number that is given explicitly to the tester.
Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set is arbitrary, and the tester is given access to a device that provides uniformly and independently distributed vertices. In addition, the tester may be (explicitly) given partial information
regarding the vertex-set (e.g., an approximation of its size).

The flexible models are more adequate for actual applications, and also facilitates the presentation of some theoretical results (e.g., reductions among property testing problems).

This programmatic note contains no real results.
It merely presents the suggested definitions and discusses them.



Changes to previous version:

A slightly different formulation of the general graph model (see Footnote 7), and fixing some typos.


Paper:

TR18-104 | 29th May 2018 17:57

Flexible models for testing graph properties





TR18-104
Authors: Oded Goldreich
Publication: 29th May 2018 17:57
Downloads: 625
Keywords: 


Abstract:

The standard models of testing graph properties postulate that the vertex-set consists of $\{1,2,...,n\}$, where $n$ is a natural number that is given explicitly to the tester.
Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set is arbitrary, and the tester is given access to a device that provides uniformly and independently distributed vertices. In addition, the tester may be (explicitly) given partial information
regarding the vertex-set (e.g., an approximation of its size).

The flexible models are more adequate for actual applications, and also facilitates the presentation of some theoretical results (e.g., reductions among property testing problems).

This programmatic note contains no real results.
It merely presents the suggested definitions and discusses them.



ISSN 1433-8092 | Imprint