Algebraic Branching Programs - Nisan's Characterization and Identity Testing

Nisan gave an exact characterization of the ``non-commutative algebraic branching program (ABP) complexity'' of a polynomial in 1991. He showed that the size of a non-commutative ABP computing a polynomial $f$ is exactly equal to the sum of ranks of the \emph{coefficient matrices} of $f$. The characterization since then has been extended to other models of computation, particularly to Read once Oblivious ABPs (ROABPs), and has motivated many interesting results.

In this talk we will first formally define ROABPs and then see a proof of Nisan's characterization. As an application, we will then proceed to see a \emph{deterministic} identity test for polynomials computed by ROABPs which is an extension of a work by Raz and Shpilka from 2005. In the remaining time (if any) we will see an overview of other models to which the characterization extends.