BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/813
DTSTAMP:20230914T125939Z
SUMMARY:Quasipolynomial Hitting Sets for Circuits With Restricted Parse Tre
 es
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nThe polynomial identity t
 esting task is to determine whether a given circuit computes the zero poly
 nomial. A hitting set for a class of circuits is a set of evaluation point
 s such that any non-zero circuit from the class outputs a non-zero value o
 n at least one of these points. Therefore finding hitting sets gives a PIT
 . The task of finding hitting sets for a class of circuits called \\emph{R
 ead-once Oblivious Algebraic Branching Programs (ROABPs)} is seen as an al
 gebraic analogue of the derandomisation of randomised logspace computation
 .\n\nLagarde\, Malod and Perifel recently introduced a class of non-commut
 ative circuits whose commutative version subsumes ROABPs. We refer to this
  commutative class as \\emph{Unique Parse Tree (UPT) set-multilinear circu
 its}. Intuitively\, an algebraic circuit belongs to this class if \\emph{a
 ll its monomials are computed identically}. In the talk we will begin by f
 ormally defining UPT set-multilinear circuits and then go into the constru
 ction of a quasi-polynomial sized hitting set for it. The construction clo
 sely follows a construction by Agrawal et al. that gives hitting sets for 
 ROABPs and thus provides more insight into the technique used by them.\n\n
 NOTE: No background on polynomial identity testing or algebraic circuits w
 ill be assumed.\n \n
URL:https://www.tcs.tifr.res.in/web/events/813
DTSTART;TZID=Asia/Kolkata:20171006T171500
DTEND;TZID=Asia/Kolkata:20171006T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR