Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions

Given Boolean functions $f,g:{\mathbb{F}}_2^n\to \{-1,+1\}$, we say they are {\em linearly isomorphic} if there exists $A\in {\mathrm{G}\mathrm{L}}_n({\mathbb{F}}_2)$ 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\in {\mathbb{F}}_2^n$ of its choice. Given parameters $\epsilon \ge 0$ and $\omega >0$, the goal is to distinguish whether there exists $A\in {\mathrm{G}\mathrm{L}}_n({\mathbb{F}}_2)$ such that the normalized Hamming distance between $f$ and $g(Ax)$ is at most $\epsilon$, or whether for every $A\in {\mathrm{G}\mathrm{L}}_n({\mathbb{F}}_2)$ the distance is at least $\epsilon +\omega$. Our main result is a tolerant tester making $\tilde{O}\left({\left(m\mathrm{/}\omega \right)}^4\right)$ queries to $f$, where $m$ is an upper bound on the spectral norm of $g$, improving the previous $\tilde{O}\left({\left(m\mathrm{/}\omega \right)}^{24}\right)$ bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of $\mathrm{\Omega }(m^2)$ for constant $\omega$ (for example, $\omega =1\mathrm{/}4$), improving the prior $\mathrm{\Omega }(\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.