Structure of sparse Boolean functions over Abelian groups, and its application to testing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918316607537152 |
|---|---|
| author | Chakraborty, Sourav Datta, Swarnalipa Dutta, Pranjal Ghosh, Arijit Sanyal, Swagato |
| author_facet | Chakraborty, Sourav Datta, Swarnalipa Dutta, Pranjal Ghosh, Arijit Sanyal, Swagato |
| contents | We study Fourier-sparse Boolean functions over general finite Abelian groups. A Boolean function $f : G \to \{-1,+1\}$ is $s$-sparse if it has at most $s$ non-zero Fourier coefficients. We introduce a general notion of granularity of Fourier coefficients and prove that every non-zero coefficient of an $s$-sparse Boolean function has magnitude at least \begin{equation*} \frac{1}{2^{φ(Δ)/2} \, s^{φ(Δ)/2}}, \end{equation*} where $Δ$ denotes the exponent of the group $G$ (that is, the maximum order of an element in $G$) and $φ$ is the Euler's totient function. This generalizes the celebrated result of Gopalan et al. (SICOMP 2011) for $\mathbb{Z}_2^n$, extending it to all finite Abelian groups via new techniques from group theory and algebraic number theory.
Using our new structural results on the Fourier coefficients of sparse functions, we design an efficient sparsity testing algorithm for Boolean functions. The tester distinguishes whether a given function is $s$-sparse or $ε$-far from every $s$-sparse Boolean function, with query complexity $poly\left((2s)^{φ(Δ)},1/ε\right)$. In addition, we generalize the classical notion of Boolean degree to arbitrary Abelian groups and establish an $Ω(\sqrt{s})$ lower bound for adaptive sparsity testing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_18700 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Structure of sparse Boolean functions over Abelian groups, and its application to testing Chakraborty, Sourav Datta, Swarnalipa Dutta, Pranjal Ghosh, Arijit Sanyal, Swagato Computational Complexity 68 F.1.3 We study Fourier-sparse Boolean functions over general finite Abelian groups. A Boolean function $f : G \to \{-1,+1\}$ is $s$-sparse if it has at most $s$ non-zero Fourier coefficients. We introduce a general notion of granularity of Fourier coefficients and prove that every non-zero coefficient of an $s$-sparse Boolean function has magnitude at least \begin{equation*} \frac{1}{2^{φ(Δ)/2} \, s^{φ(Δ)/2}}, \end{equation*} where $Δ$ denotes the exponent of the group $G$ (that is, the maximum order of an element in $G$) and $φ$ is the Euler's totient function. This generalizes the celebrated result of Gopalan et al. (SICOMP 2011) for $\mathbb{Z}_2^n$, extending it to all finite Abelian groups via new techniques from group theory and algebraic number theory. Using our new structural results on the Fourier coefficients of sparse functions, we design an efficient sparsity testing algorithm for Boolean functions. The tester distinguishes whether a given function is $s$-sparse or $ε$-far from every $s$-sparse Boolean function, with query complexity $poly\left((2s)^{φ(Δ)},1/ε\right)$. In addition, we generalize the classical notion of Boolean degree to arbitrary Abelian groups and establish an $Ω(\sqrt{s})$ lower bound for adaptive sparsity testing. |
| title | Structure of sparse Boolean functions over Abelian groups, and its application to testing |
| topic | Computational Complexity 68 F.1.3 |
| url | https://arxiv.org/abs/2406.18700 |