2025/07/10 by Datta, Swarnalipa, Ghosh, Arijit, Kayal, Chandrima +2
#06E30 #20K01 #42A16 #Computational Complexity (cs.CC) #F.1.1 #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.07654
Let f and g be Boolean functions over a finite Abelian group G, where g is fully known, and we have \em query access to f, that is, given any x ∈ G we can get the value f(x). We study the tolerant isomorphism testing problem: given ε≥ 0 and τ> 0, we seek to determine, with minimal queries, whether there exists an automorphism σ of G such that the fractional Hamming distance between f ∘ σ and g is at most ε, or whether for all automorphisms σ, the distance is at least ε+ τ. We design an efficient tolerant testing algorithm for this problem, with query complexity poly( s, 1/τ), 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.