Testing Isomorphism of Boolean Functions over Finite Abelian Groups
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913936116285440 |
|---|---|
| author | Datta, Swarnalipa Ghosh, Arijit Kayal, Chandrima Paraashar, Manaswi Roy, Manmatha |
| author_facet | Datta, Swarnalipa Ghosh, Arijit Kayal, Chandrima Paraashar, Manaswi Roy, Manmatha |
| contents | 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 $ε\geq 0$ and $τ> 0$, we seek to determine, with minimal queries, whether there exists an automorphism $σ$ of $\mathcal{G}$ such that the fractional Hamming distance between $f \circ σ$ 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 $\mathrm{poly}\left( s, 1/τ\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07654 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Testing Isomorphism of Boolean Functions over Finite Abelian Groups Datta, Swarnalipa Ghosh, Arijit Kayal, Chandrima Paraashar, Manaswi Roy, Manmatha Computational Complexity 06E30, 20K01, 42A16 F.2.2; F.1.1 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 $ε\geq 0$ and $τ> 0$, we seek to determine, with minimal queries, whether there exists an automorphism $σ$ of $\mathcal{G}$ such that the fractional Hamming distance between $f \circ σ$ 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 $\mathrm{poly}\left( s, 1/τ\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. |
| title | Testing Isomorphism of Boolean Functions over Finite Abelian Groups |
| topic | Computational Complexity 06E30, 20K01, 42A16 F.2.2; F.1.1 |
| url | https://arxiv.org/abs/2507.07654 |