Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-041 | 10th April 2008 00:00

On Proximity Oblivious Testing


Authors: Oded Goldreich, Dana Ron
Publication: 10th April 2008 19:51
Downloads: 1046


We initiate a systematic study of a special type of property testers.
These testers consist of repeating a basic test
for a number of times that depends on the proximity parameters,
whereas the basic test is oblivious of the proximity parameter.
We refer to such basic tests by the term proximity-oblivious testers.

While proximity-oblivious testers were studied before -
most notably in the algebraic setting -
the current study seems to be the first one to focus on graph properties.
We provide a mix of positive and negative results,
and in particular characterizations of the graph properties that have
constant-query proximity-oblivious testers in the two standard models
(i.e., the adjacency matrix and the bounded-degree models).
Furthermore, we show that constant-query proximity-oblivious testers
do not exist for many easily testable properties,
and that even when proximity-oblivious testers exist repeating them
does not necessarily yield the best standard testers
for the corresponding property.

ISSN 1433-8092 | Imprint