id: 05940587
dt: a
an: 05940587
au: Goldreich, Oded; Kaufman, Tali
ti: Proximity oblivious testing and the role of invariances.
so: Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea
    on the interplay between randomness and computation. In collaboration
    with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser,
    Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu
    Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman.
    Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in
    Computer Science 6650, 173-190 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: Property Testing; Graph Properties; Locally Testable Codes; Sparse Linear
    Codes; The Long-Code
ci: 
li: doi:10.1007/978-3-642-22670-0_19
ab: Summary: 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). Our focus is on the case that the
    property is characterized by a constant number of local conditions and
    a rich set of invariances. We show that, in the aforementioned models
    of testing graph properties, characterization by such invariant 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 invariant local
    conditions is neither necessary nor sufficient for proximity oblivious
    testing. Furthermore, we show that easy testability is not guaranteed
    even when the property is characterized by local conditions that are
    invariant under a 1-transitive group of permutations.
rv: