ECCC-Report TR08-041https://eccc.weizmann.ac.il/report/2008/041Comments and Revisions published for TR08-041en-usThu, 10 Apr 2008 19:51:53 +0300
Paper TR08-041
| On Proximity Oblivious Testing |
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/2008/041
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.
Thu, 10 Apr 2008 19:51:53 +0300https://eccc.weizmann.ac.il/report/2008/041