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