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