Movatterモバイル変換

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.