6 papers · 1 filter
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…
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…
Homogeneous Algebraic Complexity Theory and Algebraic Formulas
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were origi…