文章基本信息

标题：Proximity Oblivious Testing and the Role of Invariances
本地全文：下载
作者：Oded Goldreich, Tali Kaufman
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.