Revision #1 Authors: Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Accepted on: 18th April 2009 00:00

Downloads: 1996

Keywords:

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:\cube^{n}\to\cube$ satisfies this property

if $f(x),f(y),f(x+y)$ do not all equal $1$, for any pair $x,y\in\cube^{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},\ldots,v_{k}\in\cube^{k}$ and $f:\cube^{n}\to\cube$ satisfies the property that if for all linear maps $L:\cube^{k}\to\cube^{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 ``$1$-complexity linear systems''

of Green and Tao, and graphic matroids, to derive the results.

TR08-088 Authors: Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Publication: 23rd September 2008 21:10

Downloads: 1774

Keywords:

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},\ldots,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})),\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 ``1-complexity linear systems'' of

Green and Tao, and graphic matroids, to derive the results.