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 TR10-058 | 10th April 2010 17:09

Proximity Oblivious Testing and the Role of Invariances

RSS-Feed




Revision #1
Authors: Oded Goldreich, Tali Kaufman
Accepted on: 10th April 2010 17:09
Downloads: 1006
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
Downloads: 1520
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