| Title | : | On Fourier analysis of sparse Boolean functions over certain Abelian groups |
| Speaker | : | Swarnalipa Datta (ISI Kolkata) |
| Details | : | Tue, Feb 18, 2025 4:00 PM, @ Turing Hall (SSB 334) |
| Abstract | : | Given an Abelian group G, a Boolean-valued function f: G o {-1,+1}, is said to be s-sparse, if it has at most s-many non-zero Fourier coefficients over the domain G. In a seminal paper, Gopalan et al. in Testing Fourier dimensionality and sparsity proved Granularity for Fourier coefficients of Boolean valued functions over $mathbb{Z}_2^n$, that have found many diverse applications in theoretical computer science and combinatorics. They also studied structural results for Boolean functions over $mathbb{Z}_2^n$ which are approximately Fourier-sparse. In this work, we obtain structural results for approximately Fourier-sparse Boolean valued functions over Abelian groups G of the form, $G:= _{p_1}^{n_1} imes cdots imes _{p_t}^{n_t}$, for distinct primes p_i. We also obtain a lower bound of the form $1/(m^{2}s)^{lceil varphi(m)/2
ceil}$, on the absolute value of the smallest non-zero Fourier coefficient of an s-sparse function, where $m=p_1 cdots p_t$, and $varphi(m)=(p_1-1) cdots (p_t-1)$. We carefully apply probabilistic techniques from Gopalan et al., to obtain our structural results, and use some non-trivial results from algebraic number theory to get the lower bound. We construct a family of at most s-sparse Boolean functions over $_p^n$, where p > 2, for arbitrarily large enough s, where the minimum non-zero Fourier coefficient is o(1/s). The Granularity result of Gopalan et al. implies that the absolute values of non-zero Fourier coefficients of any s-sparse Boolean valued function over $mathbb{Z}_2^n$ are $Omega(1/s)$. So, our result shows that one cannot expect such a lower bound for general Abelian groups. Using our new structural results on the Fourier coefficients of sparse functions, we design an efficient sparsity testing algorithm for Boolean function, which tests whether the given function is s-sparse, or $epsilon$-far from any sparse Boolean function, and it requires $poly((ms)^{varphi(m)},1/epsilon)$-many queries. |