Testing Fourier dimensionality and sparsity.
P. Gopalan and R. O'Donnell and R. Servedio and A. Shpilka and K. Wimmer.
SIAM Journal on Computing 40(4), 2011, pp. 1075-1100.
Preliminary version in 36th International Conference on Automata, Languages and Programming (ICALP), 2009, p. 500-512.


Abstract:

We present a range of new results for testing properties of Boolean functions that are defined in terms of the Fourier spectrum. Broadly speaking, our results show that the property of a Boolean function having a concise Fourier representation is locally testable.

We first give an efficient algorithm for testing whether the Fourier spectrum of a Boolean function is supported in a low-dimensional subspace of $\F_2^n$ (equivalently, for testing whether $f$ is a junta over a small number of parities). We next give an efficient algorithm for testing whether a Boolean function has a sparse Fourier spectrum (small number of nonzero coefficients). In both cases we also prove lower bounds showing that any testing algorithm --- even an adaptive one --- must have query complexity within a polynomial factor of our algorithms, which are nonadaptive. Finally, we give an ``implicit learning'' algorithm that lets us test \emph{any} sub-property of Fourier concision.

Our technical contributions include new structural results about sparse Boolean functions and new analysis of the pairwise independent hashing of Fourier coefficients from~\cite{FGK+:06}.

pdf of conference version

pdf of journal version


Back to main papers page