Structure of sparse Boolean functions over Abelian groups, and its application to testing

Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta +2

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 coeffici…