Bhattacharyya, Arnab ;
Chen, Victor ;
Sudan, Madhu ;
Xie, Ning
Testing LinearInvariant NonLinear 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 ReedMuller 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:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$ satisfies this property if $f(x),f(y),f(x+y)$ do not all equal $1$, for any pair $x,y\in\mathbb{F}_{2}^{n}$.
Here we extend this test to a more systematic study of testing for linearinvariant nonlinear 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},\ldots,v_{k}\in\mathbb{F}_{2}^{k}$ and $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$ satisfies the property that if for all linear maps $L:\mathbb{F}_{2}^{k}\to\mathbb{F}_{2}^{n}$ it is the case that $f(L(v_{1})),\ldots,f(L(v_{k}))$ do not all equal $1$. We show that this property is testable if the underlying matroid specified by $v_{1},\ldots,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 {}``1complexity linear systems'' of Green and Tao, and graphic matroids, to derive the results.
BibTeX  Entry
@InProceedings{bhattacharyya_et_al:LIPIcs:2009:1823,
author = {Arnab Bhattacharyya and Victor Chen and Madhu Sudan and Ning Xie},
title = {{Testing LinearInvariant NonLinear Properties}},
booktitle = {26th International Symposium on Theoretical Aspects of Computer Science},
pages = {135146},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897095},
ISSN = {18688969},
year = {2009},
volume = {3},
editor = {Susanne Albers and JeanYves Marion},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1823},
URN = {urn:nbn:de:0030drops18235},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1823},
annote = {Keywords: }
}
Seminar: 

26th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2009 
Date of publication: 

19.02.2009 