BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/954
DTSTAMP:20230914T125944Z
SUMMARY:Closure of Small Circuits Under Taking Factors
DESCRIPTION:Speaker: Prerona  Chatterjee\n\nAbstract: \nAbstract: In the 19
 80s\, Kaltofen proved one of the most remarkable results in algebraic comp
 lexity theory. He showed that if a polynomial can be computed by a small c
 ircuit\, then each of its factors can also be computed by small circuits. 
 In fact\, given a circuit for the original polynomial\, he also gave an ef
 ficient algorithm for computing circuits for the factors. This result has 
 many applications\, one of which is the algebraic analogue of the hardness
  vs randomness question.\nIn most applications\, however\, it is only requ
 ired to show the existence of small circuits for the factors (as opposed t
 o actually computing them). Very recently\, Mrinal Kumar\, Chi-Ning Chou a
 nd Noam Solomon gave a short\, simple and almost completely self contained
  proof of this fact\, and in this talk we will discuss their proof. Formal
 ly\, we will prove the following statement.\n\nIf an n variate degree d po
 lynomial f can be computed by an algebraic circuit of size s\, then each o
 f its factors can be computed by an algebraic circuit of size at most poly
 (s\, n\, d).\n
URL:https://www.tcs.tifr.res.in/web/events/954
DTSTART;TZID=Asia/Kolkata:20190405T171500
DTEND;TZID=Asia/Kolkata:20190405T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR