Testing Isomorphism of Boolean Functions over Finite Abelian Groups

Title of the Talk: Testing Isomorphism of Boolean Functions over Finite Abelian Groups
Speakers: Swarnalipa Datta (ISI, Kolkata)
Host Faculty: Nitin Saurabh
Date: Aug 05, 2025
Time: 02:30 pm to 3:30pm
Venue: C-LH-10

Abstract:

Let f and g be Boolean functions over a finite Abelian group G, where g is fully known and we have query access to f, i.e., for any x∈G, we can obtain f(x). We study the tolerant isomorphism testing problem: given ε≥0and τ>0, determine — using as few queries as possible — whether there exists an automorphism σ of G such that the fractional Hamming distance between f∘σ and g is at most ε, or whether for all such σ, the distance is at least ε+τ.

We design an efficient tolerant testing algorithm for this problem, with query complexity polynomial in s and 1/τ, where s bounds the spectral norm of g.

Our techniques draw on tools from Abelian group theory and Fourier analysis, including the annihilator of a subgroup, Pontryagin duality, and a pseudo inner product defined over finite Abelian groups. This is a joint work with Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy.