Testing Isomorphism of Boolean Functions over Finite Abelian Groups

Abstract

Let $f$ and $g$ be Boolean functions over a finite Abelian group $\mathcal{G}$, where $g$ is fully known, and we have {\em query access} to $f$, that is, given any $x\in \mathcal{G}$ we can get the value $f(x)$. We study the tolerant isomorphism testing problem: given $\hat{I}\mu \ge 0$ and $\ddot{I}„>0$, we seek to determine, with minimal queries, whether there exists an automorphism $\ddot{I}ƒ$ of $\mathcal{G}$ such that the fractional Hamming distance between $f\circ \ddot{I}ƒ$ and $g$ is at most $\hat{I}\mu$, or whether for all automorphisms $\ddot{I}ƒ$, the distance is at least $\hat{I}\mu +\ddot{I}„$. We design an efficient tolerant testing algorithm for this problem, with query complexity $\mathrm{poly}\left(s,1/\ddot{I}„\right)$, where $s$ bounds the spectral norm of $g$. Additionally, we present an improved algorithm when $g$ is Fourier sparse. Our approach uses key concepts from Abelian group theory and Fourier analysis, including the annihilator of a subgroup, Pontryagin duality, and a pseudo inner-product for finite Abelian groups. We believe these techniques will find further applications in property testing.

44 pages, RANDOM 2025