A unified framework for testing linear‐invariant properties |
| |
| Authors: | Arnab Bhattacharyya Elena Grigorescu Asaf Shapira |
| |
| Affiliation: | 1. DIMACS, Piscataway, New Jersey;2. Department of Computer Science, Purdue University, West Lafayette, Indiana;3. School of Mathematics, Tel‐Aviv University, Tel‐Aviv, Israel;4. Schools of Mathematics and Computer, Georgia Institute of Technology, Atlanta, Georgia |
| |
| Abstract: | 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. Our main contributions here are the following:
| |
| Keywords: | property testing linear invariance subspace‐hereditary properties |
|
|
