Price of Parsimony: Complexity of Fourier Sparsity Testing
Manmatha Roy, Arijit Ghosh
A function \( f : \mathbb{F}_2^n \to \mathbb{R} \) is said to be \( s \)-Fourier sparse if its Fourier expansion contains at most \( s \) non-zero coefficients. Fourier sparsity is a key structural property that facilitates efficient representation, computation, and learning of functions. In general, the existence of a sparse representation in the Fourier basis facilitates the development of efficient learning algorithms. However, most of these techniques rely on prior knowledge of the function's Fourier sparsity, with the algorithmic parameters tailored based on this information.This motivates the following decision problem: given \( s > 0 \), determine whether a given function is (approximately) \( s \)-Fourier sparse.This work addresses the problem of tolerant testing of real-valued functions over $\mathbb{F}_2^n$, accessed via queries, to determine whether the function is close to being $s$-Fourier sparse or significantly far from every $s$-Fourier sparse function. Building on the \emph{distance approximation via tolerant testing} framework developed by Parnas et al., our tester naturally yields an estimator that, given oracle access to the function, approximates its distance to the closest $s$-Fourier sparse function, with formal guarantees on both accuracy and confidence. Our algorithm has query complexity $\widetilde{O}(s)$ for constant accuracy and confidence parameters.A key structural ingredient in our analysis is a new spectral concentration result for real-valued functions defined over $\mathbb{F}_2^n$ under restriction to small-dimensional random affine subspaces. We complement our upper bound with a matching lower bound of $\Omega(s)$, showing that our tester is optimal up to logarithmic factors. Our lower bound leverages spectral properties of a certain class of cryptographically hard functions, known as the Maiorana–McFarland class, in a novel way.