4 papers
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 is -sparse if it has at most non-zero Fourier coeffici…
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
Given Boolean functions \( f, g : \mathbb{F}_2^n \to \{-1,+1\} \), we say they are {\em linearly isomorphic} if there exists \( A \in \mathrm{GL}_n(\mathbb{F}_2) \) such that \( f(…
Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
In this short note, we initiate the study of the Linear Isomorphism Testing Problem in the setting of communication complexity, a natural linear algebraic generalization of the cla…
Testing Isomorphism of Boolean Functions over Finite Abelian Groups
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
Let and be Boolean functions over a finite Abelian group , where is fully known, and we have {\em query access} to , that is, given any $x \in \mathcal{…