3 papers
cs.CC2021
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…
cs.DS2021
Generalized Parametric Path Problems
Prerona Chatterjee, Kshitij Gajjar, Jaikumar Radhakrishnan +1
Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general pa…
cs.CC2019
A Quadratic Lower Bound for Algebraic Branching Programs and Formulas
Prerona Chatterjee, Mrinal Kumar, Adrian She +1
We show that any Algebraic Branching Program (ABP) computing the polynomial has at least vertices. This improves upon the lower bound of $Ω(n\log n)…