Testing Isomorphism of Boolean Functions over Finite Abelian Groups

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, Manmatha Roy

Introduction

In the field of property testing, the goal is to determine whether a mathematical object possesses a specific property by examining only a small, random sample of its values. A fundamental problem in this domain is Function Isomorphism Testing (FIT). Given a known function $g$ and an unknown function $f$, the objective is to decide if $f$ is "isomorphic" to $g$—that is, whether $f(x) = g(\sigma(x))$ for some symmetry or automorphism $\sigma$ of the underlying domain.

Historically, research into FIT has focused heavily on functions defined over the vector space $\mathbb{Z}_2^n$. In such cases, the symmetries are restricted to linear transformations, and the problem benefits from the rigid structure of linear algebra. However, many mathematical and computational structures are better represented as finite Abelian groups (e.g., $\mathbb{Z}_{10} \times \mathbb{Z}_{15}$), which do not necessarily possess a vector space structure. This paper provides the first efficient algorithm for testing isomorphism over any finite Abelian group, specifically addressing the "tolerant" version of the problem: distinguishing functions that are very close to an isomorphic copy from those that are significantly distant.

Technical Challenges and Methodology

Transitioning from vector spaces to general Abelian groups introduces significant technical hurdles. The authors overcome these by developing group-theoretic analogs for classical linear algebraic tools.

1. Generalizing the Implicit Sieve

The authors extend the "Implicit Sieve" algorithm, originally designed for vector spaces, to work with the characters of any finite Abelian group. This allows the algorithm to identify the most influential components of a function's Fourier transform without prior knowledge of the function's specific structure.

2. Pseudo-Inner Products and Independence

Because general Abelian groups lack a standard basis, the authors introduce the concepts of pseudo-inner products and pseudo-independence. These tools allow the algorithm to mimic the behavior of linear independence, providing a way to navigate the group structure even when traditional basis-dependent methods fail.

3. Annihilators and Pontryagin Duality

To replace the role of orthogonal complements used in vector space analysis, the paper utilizes Pontryagin duality. Specifically, they employ the concept of a subgroup's annihilator—the set of characters that evaluate to 1 for every element in that subgroup. This provides a robust framework for handling dual structures within the group.

4. Managing Complex Characters

Unlike functions over $\mathbb{Z}_2^n$, where Fourier coefficients are real numbers, general Abelian groups involve complex-valued characters (roots of unity). The authors developed a novel approach to handle these complex values, as traditional methods relying on the "sign" of a coefficient are inapplicable in the complex plane.

Key Insights: The Centrality of the Spectral Norm

A primary contribution of this work is the realization that the difficulty of testing isomorphism is not determined by the size of the group, but rather by the complexity of the function itself. The authors show that the spectral norm ($s$) of the known function $g$ is the dominant factor in determining query complexity. If a function is "simple" in the Fourier domain (possessing a low spectral norm), it can be tested efficiently regardless of how massive the underlying group $\mathcal{G}$ might be.

Furthermore, the algorithm is "tolerant," meaning it is robust against noise. It can successfully distinguish between functions that are nearly isomorphic and those that are far from any isomorphic transformation, making the approach more applicable to real-world scenarios where data may be imperfect.

Results and Complexity

The paper establishes new upper bounds for the query complexity of isomorphism testing over finite Abelian groups:

  • General Bound: The authors present a randomized algorithm with a query complexity of $\tilde{O}(s^8 / \tau^8)$, where $s$ is the spectral norm and $\tau$ is the distance parameter. This complexity is entirely independent of the group size $|\mathcal{G}|$.
  • Fourier Sparse Functions: For functions that are "Fourier sparse" (having only $s$ non-zero coefficients), the query complexity is improved to $\tilde{O}(s^4 / \tau^4)$.
  • Unified Framework: By providing results that hold for any finite Abelian group, the authors offer a unified framework for problems that were previously treated as distinct special cases.

Limitations and Future Directions

While this work represents a significant theoretical leap, it leaves several avenues for future research. The polynomial exponents in the complexity bounds (up to 8) are relatively high, suggesting that further optimization is possible to make the algorithms more practical for functions with larger spectral norms.

Additionally, the current framework is strictly limited to Abelian (commutative) groups. Extending isomorphism testing to non-Abelian groups remains a major challenge, as it would require moving beyond standard Fourier analysis into the more complex realm of representation theory. Finally, the authors suggest that their "pseudo-inner product" and "annihilator" techniques may be applicable to other property testing problems, such as testing for specific algebraic symmetries or structures beyond simple isomorphism.

Summary updated

Abstract

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.
BibTeX
@inproceedings{datta2025testing,
  author = {Swarnalipa Datta and Arijit Ghosh and Chandrima Kayal and Manaswi Paraashar and Manmatha Roy},
  title = {{Testing Isomorphism of Boolean Functions over Finite Abelian Groups}},
  booktitle = {APPROX/RANDOM},
  year = {2025},
  url = {https://openreview.net/forum?id=R6iprmD18G},
}
Figure