Theory of Computing
-------------------
Title : Testing Linear-Invariant Non-Linear Properties
Authors : Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie
Volume : 7
Number : 6
Pages : 75-99
URL : https://theoryofcomputing.org/articles/v007a006
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 --> {0,1} has
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 --> 0,1 has the property that if for all linear maps
L: F_2^k --> 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.
Part of our main results was obtained independently by Kral', Serra,
and Venna [Journal of Combinatorial Theory Series A, 116 (2009),
pp. 971--978].
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.