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{GL}_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 \( ε\ge 0 \) and \( ω>0 \), the goal is to distinguish whether there exists \( A \in \mathrm{GL}_n(\mathbb{F}_{2})\) such that the normalized Hamming distance between \( f \) and \( g(Ax) \) is at most \( ε\), or whether for every \( A \in \mathrm{GL}_n(\mathbb{F}_2) \) the distance is at least \( ε+ω\). Our main result is a tolerant tester making \( \widetilde{O} \left( \left( m/ω\right)^4 \right) \) queries to \( f \), where \( m \) is an upper bound on the spectral norm of \( g \), improving the previous \( \widetilde{O} \left( \left( m/ω\right)^{24} \right) \) bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of \( Ω(m^2) \) 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.