A unified framework for testing linear‐invariant properties12. Issue 2 (27th June 2013)

• Record Type: Journal Article
• Authors: Bhattacharyya, Arnab; Grigorescu, Elena; Shapira, Asaf
• Is Part Of: Random structures & algorithms. Volume 46:Issue 2(2015)
• Page Start: 232
• Page End: 260
• Publication Date: 2013-06-27
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20507
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>In the study of property testing, a particularly important role has been played by linear invariant properties, i.e., properties of Boolean functions on the hypercube which are closed under linear transformations of the domain. Examples of such properties include linearity, Reed‐Muller codes, and Fourier sparsity. In this work, we describe a framework that can lead to a unified analysis of the testability of all linear‐invariant properties, drawing on techniques from additive combinatorics and from graph theory.</p> <p>Our main contributions here are the following: <list id="rsa20507-list-0001" list-type="order"><list-item id="rsa20507-li-0001"><p>We introduce a simple combinatorial condition, which we call <italic>subspace‐heredity</italic>, and conjecture that any property of Boolean functions satisfying it can be efficiently tested. Verifying this conjecture will unify many individual results in this area.</p></list-item><list-item id="rsa20507-li-0002"><p>We show that if our conjecture holds, then one can obtain a simple combinatorial <italic>characterization</italic> of properties of Boolean functions that can be efficiently tested with one‐sided error, thus addressing a challenge posed by Sudan recently.</p></list-item><list-item id="rsa20507-li-0003"><p>We introduce a new technique for proving the testability of Boolean functions. The main tool we develop is an extension of Green's arithmetic regularity lemma. Using it, we verify a special case of the conjecture.</p></list-item></list></p> <p>Our approach here is motivated by techniques that proved to be very successful previously in studying the testability of graph properties.© 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 232–260, 2015</p> </abstract>