BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/788
DTSTAMP:20230914T125938Z
SUMMARY:Algebraic Branching Programs - Nisan's Characterization and Identit
y Testing
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nNisan gave an exact chara
cterization of the ``non-commutative algebraic branching program (ABP) com
plexity'' of a polynomial in 1991. He showed that the size of a non-commut
ative ABP computing a polynomial $f$ is exactly equal to the sum of ranks
of the \\emph{coefficient matrices} of $f$. The characterization since the
n has been extended to other models of computation\, particularly to Read
once Oblivious ABPs (ROABPs)\, and has motivated many interesting results.
\n\nIn 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 ROAB
Ps which is an extension of a work by Raz and Shpilka from 2005. In the re
maining time (if any) we will see an overview of other models to which the
characterization extends.\n
URL:https://www.tcs.tifr.res.in/web/events/788
DTSTART;TZID=Asia/Kolkata:20170623T171500
DTEND;TZID=Asia/Kolkata:20170623T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR