Florida International University
Edit Your Profile
FIU Discovery
Toggle navigation
Browse
Home
People
Organizations
Scholarly & Creative Works
Research Facilities
Support
Edit Your Profile
Testing linear-invariant non-linear properties
Conference
Bhattacharyya, A, Chen, V, Sudan, M
et al
. (2009). Testing linear-invariant non-linear properties .
3 135-146.
Share this citation
Twitter
Email
Bhattacharyya, A, Chen, V, Sudan, M
et al
. (2009). Testing linear-invariant non-linear properties .
3 135-146.
Copy Citation
Share
Overview
Additional Document Info
View All
Overview
cited authors
Bhattacharyya, A; Chen, V; Sudan, M; Xie, N
authors
Xie, Ning
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 2n → F2 satisfies this property if f(x),f(y),f(x + y) do not all equal 1, for any pair x,y ∈ F 2n. Here we extend this test to a more systematic study of testing for linear-invariant nonlinear 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 v1,⋯,vk ∈ F2k and f: F2n → F 2 satisfies the property that if for all linear maps L: F 2k → F2n it is the case that f(L(v1)),⋯,f(L(vk)) do not all equal 1. We show that this property is testable if the underlying matroid specified by v 1,⋯,vk 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. © A. Bhattacharyya, V. Chen, M. Sudan, and N. Xie.
publication date
December 1, 2009
Additional Document Info
start page
135
end page
146
volume
3