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