ECCC-Report TR08-088https://eccc.weizmann.ac.il/report/2008/088Comments and Revisions published for TR08-088en-usSat, 18 Apr 2009 00:00:00 +0300
Revision 1
| Testing Linear-Invariant Non-Linear Properties |
Arnab Bhattacharyya,
Victor Chen,
Madhu Sudan,
Ning Xie
https://eccc.weizmann.ac.il/report/2008/088#revision1We 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.
Sat, 18 Apr 2009 00:00:00 +0300https://eccc.weizmann.ac.il/report/2008/088#revision1
Paper TR08-088
| Testing Linear-Invariant Non-Linear Properties |
Arnab Bhattacharyya,
Victor Chen,
Madhu Sudan,
Ning Xie
https://eccc.weizmann.ac.il/report/2008/088We 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.
Tue, 23 Sep 2008 21:10:19 +0300https://eccc.weizmann.ac.il/report/2008/088