BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1071
DTSTAMP:20230914T125949Z
SUMMARY:The class of poly-sized Algebraic Branching Programs is closed unde
r Factoring
DESCRIPTION:Speaker: Prerona Chatterjee\n\nAbstract: \nTalk will be held i
n Zoom.\nAbstract: In the 1980s\, Kaltofen proved one of the most remar
kable results in algebraic complexity theory. He showed that if a polynomi
al can be computed by a "small" circuit\, then each of its factors can als
o be computed by "small" circuits. In fact\, given a circuit for the origi
nal polynomial\, he also gave an efficient algorithm for computing circuit
s for the factors. This result has many applications\, one of which is the
algebraic analogue of the "hardness vs randomness" question.\n\nHowever\,
his proof did not extend to more restricted models of computation. Recent
ly Amit Sinhababu and Thomas Thierauf showed a similar statement for the c
lass of Algebraic Branching Programs (or ABPs). Formally\, they proved the
following statement. If an n variate degree d polynomial f can be compute
d by an ABP of size s\, then each of its factors can be computed by an ABP
of size at most poly(s\, n\, d).\nIn this talk\, we will go over the proo
f techniques used in the previous results of this kind\, and see an overvi
ew of the modifications Sinhababu and Theirauf made to these techniques to
get their result.\n\nNo background of the field will be assumed.\n
URL:https://www.tcs.tifr.res.in/web/events/1071
DTSTART;TZID=Asia/Kolkata:20200718T160000
DTEND;TZID=Asia/Kolkata:20200718T170000
END:VEVENT
END:VCALENDAR