BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/708
DTSTAMP:20230914T125935Z
SUMMARY:On Polynomial Approximations to AC0
DESCRIPTION:Speaker: Prahladh  Harsha\n\nAbstract: \nIn this talk\, we will
  survey questions related to polynomial approximations of AC0. A classic r
 esult due to Tarui (1991) and Beigel\, Reingold\, and Spielman (1991)\, th
 at any AC0 circuit of size s and depth d has an ε-error probabilistic pol
 ynomial over the reals of degree (log(s/ε))^{O(d)}. We will have a re-loo
 k at this construction and show how to improve the bound to (log s)^{O(d)}
 ⋅log(1/ε)\, which is much better for small values of ε.\n\nAs an appli
 cation of this result\, we show that (log s)^{O(d)}⋅log(1/ε)-wise indep
 endence fools AC0\, improving on Tal's strengthening of Braverman's theore
 m that (log(s/ε))^{O(d)}-wise independence fools AC0. Time permitting\, w
 e will also discuss some lower bounds on the best polynomial approximation
 s to AC0 (joint work with Srikanth Srinivasan).\n \n
URL:https://www.tcs.tifr.res.in/web/events/708
DTSTART;TZID=Asia/Kolkata:20160830T163000
DTEND;TZID=Asia/Kolkata:20160830T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR