4 papers · 1 filter
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 $σ…
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…
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…
Fixed-parameter debordering of Waring rank
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
Border complexity measures are defined via limits (or topological closures), so that any function which can approximated arbitrarily closely by low complexity functions itself has…