Speaker: | Swarnalipa Datta (ISI Kolkata) |
Organiser: | Raghuvansh Saxena |
Date: | Monday, 23 Dec 2024, 16:00 to 17:00 |
Venue: | A-201 (STCS Seminar Room) |
We construct a family of at most s-sparse Boolean functions over $\mathbb{Z}_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 $\mathrm{poly}((ms)^{\varphi(m)},1/\epsilon)$-many queries.
Short Bio: Swarnalipa Datta is a Senior Research Fellow in Computer Science at the Indian Statistical Institute, Kolkata, working under the supervision of Dr. Sourav Chakraborty and Dr. Arijit Ghosh on the Fourier analysis of Boolean functions. Swarnalipa completed a Bachelor's in Mathematics from St. Xavier's College, Kolkata, and a Master's in Mathematics from the Indian Institute of Science, Bangalore.