2026-07-20T11:15:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24432 2025-12-12T15:01:49Z ddc:004 open_access

Testing Isomorphism of Boolean Functions over Finite Abelian Groups Datta, Swarnalipa Ghosh, Arijit Kayal, Chandrima Paraashar, Manaswi Roy, Manmatha Analysis of Boolean functions Abelian groups Automorphism group Function isomorphism Spectral norm Let f and g be Boolean functions over a finite Abelian group 𝒢, where g is fully known and f is accessible via queries; that is, given any x ∈ 𝒢, we can obtain the value f(x). We study the problem of tolerant isomorphism testing: given parameters ε ≥ 0 and τ > 0, the goal is to determine, using as few queries as possible, whether there exists an automorphism σ of 𝒢 such that the fractional Hamming distance between f∘σ and g is at most ε, or whether for every automorphism σ, the distance is at least ε + τ. We design an efficient tolerant property testing algorithm for this problem over finite Abelian groups with constant exponent. The exponent of a finite group refers to the largest order of any element in the group. The query complexity of our algorithm is polynomial in s and 1/τ, where s bounds the spectral norm of the function g, and τ is the tolerance parameter. In addition, we present an improved algorithm in the case where g is Fourier sparse, meaning that its Fourier expansion contains only a small number of nonzero coefficients. Our approach draws on key ideas 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. We believe that these techniques will be useful more broadly in the design of property testing algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Swarnalipa Datta and Arijit Ghosh and Chandrima Kayal and Manaswi Paraashar and Manmatha Roy 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.66 urn:nbn:de:0030-drops-244328 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.66 eng https://creativecommons.org/licenses/by/4.0/legalcode