Tata Institute of Fundamental Research

Algebraic Branching Programs - Nisan's Characterization and Identity Testing

STCS Student Seminar
Speaker: Anamay Tengse
Organiser: Nikhil S Mande
Date: Friday, 23 Jun 2017, 17:15 to 18:15
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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.