摘要：We consider the task of testing properties of Boolean functions thatare invariant under linear transformations of the Boolean cube. Previouswork in property testing, including the linearity test and the testfor Reed-Muller codes, has mostly focused on such tasks for linearproperties. The one exception is a test due to Green for “triangle freeness:”a function $f:\mathbb{F}_{2}^{n}\to \{0,1\}$ has this propertyif $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 forlinear-invariant non-linear properties. We consider properties thatare 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 \{0,1\}$ has the property that if for alllinear 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 theunderlying matroid specified by $v_{1},\ldots,v_{k}$ is a graphicmatroid. This extends Green's result to an infinite class of new properties.Part of our main results was obtained independently by Král', Serra, and Venna [Journal of Combinatorial Theory Series A, 116 (2009), pp 971--978].Our techniques extend those of Green and in particular we establisha link between the notion of “$1$-complexity linear systems”of Green and Tao, and graphic matroids, to derive the results.
