Given Boolean functions f, g : 𝔽₂ⁿ → {-1,+1}, we say they are linearly isomorphic if there exists A ∈ GL_n(𝔽₂) such that f(x) = g(Ax) for all x. We study this problem in the tolerant property testing framework under the known-unknown model, where g is given explicitly and f is accessible only via oracle queries, meaning the algorithm may adaptively request the value of f(x) for inputs x ∈ 𝔽₂ⁿ of its choice. Given parameters ε ≥ 0 and ω > 0, the goal is to distinguish whether there exists A ∈ GL_n(𝔽₂) such that the normalized Hamming distance between f and g(Ax) is at most ε, or whether for every A ∈ GL_n(𝔽₂) the distance is at least ε+ω. Our main result is a tolerant tester making Õ ((m/ω) ⁴) queries to f, where m is an upper bound on the spectral norm of g, improving the previous Õ ((m/ω) ^{24}) bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of Ω(m²) for constant ω (for example, ω = 1/4), improving the prior Ω(log m) lower bound of Grigorescu, Wimmer and Xie. A key technical ingredient on the algorithmic side is a query-efficient local list corrector. For the lower bound, we give a reduction from communication complexity using a novel subclass of Maiorana-McFarland functions from symmetric-key cryptography.

International audience

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 \) nonzero coefficients. In general, the existence of a sparse representation in the Fourier basis serves as a key enabler for the design of efficient learning algorithms. However, most existing techniques assume prior knowledge of the function’s Fourier sparsity, with algorithmic parameters carefully tuned to this value. This motivates the following decision problem: given \( s > 0 \), determine whether a function is \( s \)-Fourier sparse. In this work, we study the problem of tolerant testing of Fourier Sparsity for real-valued functions over \( \mathbb{F}_2^n \), accessed via oracle queries. The goal is to decide whether a given function is close to being \( s \)-Fourier sparse or far from every \( s \)-Fourier sparse function. Our algorithm provides an estimator that, given oracle access to the function, estimates its distance to the nearest \( s \)-Fourier sparse function with 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 over \( \mathbb{F}_2^n \) when restricted to small-dimensional random affine subspaces. We further complement our upper bound with a matching lower bound of \( \Omega(s) \), establishing that our tester is optimal up to logarithmic factors. The lower bound exploits spectral properties of a class of cryptographically hard functions, namely, the Maiorana--McFarland family, in a novel way.