1 citations · 1 across the 6 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.CC2023
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 (…
cs.CC2023
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.CC2023
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…