2 papers
cs.CC2024
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 $Ï…
cs.CC2024
Explicit Commutative ROABPs from Partial Derivatives
Vishwas Bhargava, Anamay Tengse
The dimension of partial derivatives (Nisan and Wigderson, 1997) is a popular measure for proving lower bounds in algebraic complexity. It is used to give strong lower bounds on th…