Showing cs.CCShow all
2 papers · 1 filter
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.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)…