BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/866
DTSTAMP:20230914T125941Z
SUMMARY:A "Simple" Class of Algebraic Circuits
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nIn this talk we will look
  at $n$-variate polynomials that can be expressed as a small (poly$(n)$) s
 um of powers of linear polynomials. That is\, polynomials that have effici
 ent {\\em depth-3-powering} circuits.\nWe will see an exp$(n)$ lower bound
  against this model for the {\\em monomial} $x_1 x_2 \\cdots x_n$\, and al
 so an almost matching upper bound using {\\em Fischer's trick}. We will th
 en extend the ideas in the lower bound to obtain an $n^{O(\\log n)}$ sized
  hitting set (Forbes-Shpilka '13).\nDepending on the time left\, we will s
 ketch an $n^{O(\\log \\log n)}$ sized hitting set construction (Forbes-Shp
 ilka-Saptharishi '14).\n
URL:https://www.tcs.tifr.res.in/web/events/866
DTSTART;TZID=Asia/Kolkata:20180420T171500
DTEND;TZID=Asia/Kolkata:20180420T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR