1 citations · 1 across the 5 of their papers we have counts for
9 papers
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…
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…
Monotone Classes Beyond VNP
Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran and Perifel 2009, Malod 2011, Mahajan…
On Finer Separations between Subclasses of Read-once Oblivious ABPs
C. Ramya, Anamay Tengse
Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand…
If VNP is hard, then so are equations for it
Mrinal Kumar, C. Ramya, Ramprasad Saptharishi +1
Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, a…
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…
Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees
Ramprasad Saptharishi, Anamay Tengse
We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introdu…