Testing Linear-Invariant Non-Linear Properties

Details Testing Linear-Invariant Non-Linear Properties Testing Linear-Invariant Non-Linear Properties

2008-09-14

arxiv.org/abs/0809.2378v2

Mathematics

Combinatorics

This is the full version; conference version appeared in the proceedings of STACS 2009

Scientific paper

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},...,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})),...,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.

Affiliated with

Also associated with

No associations

Rating

Testing Linear-Invariant Non-Linear Properties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing Linear-Invariant Non-Linear Properties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing Linear-Invariant Non-Linear Properties will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-156137