Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR10-058 | 10th April 2010 17:09

#### Proximity Oblivious Testing and the Role of Invariances

Revision #1
Authors: Oded Goldreich, Tali Kaufman
Accepted on: 10th April 2010 17:09
Keywords:

Abstract:

We present a general notion of properties that
are characterized by local conditions that are invariant
under a sufficiently rich class of symmetries.
Our framework generalizes two popular models of
testing graph properties as well as the algebraic
invariances studied by Kaufman and Sudan (STOC'08).

We show that, in the aforementioned models of
testing graph properties, characterization by
such invaraint local conditions is closely
related to proximity oblivious testing
(as defined by Goldreich and Ron, STOC'09).
In contrast to this relation, we show that, in general,
characterization by invaraint local conditions
is neither necessary nor sufficient
for proximity oblivious testing.
Furthermore, we show that easy testability is {\em not}\/ guaranteed
even when the property is characterized by local conditions
that are invariant under a 1-transitive group of permutations.

Changes to previous version:

Merely correcting numerous typos (spelling mistakes). Oded

### Paper:

TR10-058 | 7th April 2010 12:56

#### Proximity Oblivious Testing and the Role of Invariances

TR10-058
Authors: Oded Goldreich, Tali Kaufman
Publication: 7th April 2010 12:56
Keywords:

Abstract:

We present a general notion of properties that
are characterized by local conditions that are invariant
under a sufficiently rich class of symmetries.
Our framework generalizes two popular models of
testing graph properties as well as the algebraic
invariances studied by Kaufman and Sudan (STOC'08).

We show that, in the aforementioned models of
testing graph properties, characterization by
such invaraint local conditions is closely
related to proximity oblivious testing
(as defined by Goldreich and Ron, STOC'09).
In contrast to this relation, we show that, in general,
characterization by invaraint local conditions
is neither necessary nor sufficient
for proximity oblivious testing.
Furthermore, we show that easy testability is {\em not}\/ guaranteed
even when the property is characterized by local conditions
that are invariant under a 1-transitive group of permutations.

ISSN 1433-8092 | Imprint