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.

No reviews yet.

No comments yet.