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…
Recent Advances in Debordering Methods
Pranjal Dutta, Vladimir Lysikov
Border complexity captures functions that can be approximated by low-complexity ones. Debordering is the task of proving an upper bound on some non-border complexity measure in ter…
Algebraic metacomplexity and representation theory
Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo +2
In the algebraic metacomplexity framework we prove that the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasi…
The Complexity of Order-Finding for ROABPs
Vishwas Bhargava, Pranjal Dutta, Sumanta Ghosh +1
We study the \emph{order-finding problem} for Read-once Oblivious Algebraic Branching Programs (ROABPs). Given a polynomial and a parameter , the goal is to find an order $Ï…