Testing Linear-Invariant Non-Linear Properties

Abstract : We consider the task of testing properties of Boolean functions that are invariant under linear transformations of the Boolean cube. Previous work in property testing, including the linearity test and the test for Reed-Muller codes, has mostly focused on such tasks for linear properties. The one exception is a test due to Green for {}triangle freeness'': A function f: F_{2}^{n} \to F_{2} satisfies this property if f(x),f(y),f(x+y) do not all equal 1, for any pair x,y in F_{2}^{n}. Here we extend this test to a more systematic study of testing for linear-invariant non-linear properties. We consider properties that are described by a single forbidden pattern (and its linear transformations), i.e., a property is given by k points v_{1},...,v_{k} in F_{2}^{k} and f: F_{2}^{n} to F_{2} satisfies the property that if for all linear maps L: F_{2}^{k} to F_{2}^{n} it is the case that f(L(v_{1})),..., f(L(v_{k})) do not all equal 1. We show that this property is testable if the underlying matroid specified by v_{1},... ,v_{k} is a graphic matroid. This extends Green's result to an infinite class of new properties. Our techniques extend those of Green and in particular we establish a link between the notion of 1-complexity linear systems'' of Green and Tao, and graphic matroids, to derive the results.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.135-146, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Domaine :

Littérature citée [28 références]

https://hal.inria.fr/inria-00359022
Contributeur : Publications Loria <>
Soumis le : lundi 9 février 2009 - 09:56:20
Dernière modification le : jeudi 12 février 2009 - 15:35:39
Document(s) archivé(s) le : mardi 8 juin 2010 - 21:55:28

Fichiers

Bhattacharyya_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

• HAL Id : inria-00359022, version 1

Citation

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie. Testing Linear-Invariant Non-Linear Properties. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.135-146, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359022〉

Métriques

Consultations de la notice

156

Téléchargements de fichiers