1 citations · 1 across the 6 of their papers we have counts for
10 papers
IPS Lower Bounds for Formulas and Sum of ROABPs
Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay +1
We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic pro…
Lower Bounds for Set-Multilinear Branching Programs
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf +1
In this paper, we prove super-polynomial lower bounds for the model of \emph{sum of ordered set-multilinear algebraic branching programs}, each with a possibly different ordering (…
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…
New Lower Bounds against Homogeneous Non-Commutative Circuits
Prerona Chatterjee, Pavel Hrubeš
We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree which requires homogeneous n…
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…
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting
Prerona Chatterjee
The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in t…