3 papers
cs.CC2025
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…
cs.CC2025
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…
cs.CC2025
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…