5 papers
Lower Bounds from Succinct Hitting Sets
Prerona Chatterjee, Anamay Tengse
We investigate the consequences of the existence of ``efficiently describable'' hitting sets for polynomial sized algebraic circuit (), in particular, \emph{$\mathsf{V…
On the Existence of Algebraic Natural Proofs
Prerona Chatterjee, Mrinal Kumar, C Ramya +2
The framework of algebraically natural proofs was independently introduced in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), to study the…
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse
The Polynomial Ident…
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 $Ï…
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…