On Proximity Oblivious Testing

Webpage for a paper by Oded Goldreich and Dana Ron


Abstract

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.

Material available on-line

See related paper on two-sided error POTs.


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