BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/932
DTSTAMP:20230914T125944Z
SUMMARY:Some Closure Results for Polynomial Factorization and Applications
DESCRIPTION:Speaker: Mrinal Kumar (Simons Institute for the\nTheory of Comp
uting\nBerkeley\, CA 94720-2190)\n\nAbstract: \nAbstract : In a sequence
of seminal results in the 80's\, Kaltofen showed that if an n-variate poly
nomial of degree poly(n) can be computed by an arithmetic circuit of size
poly(n)\, then each of its factors can also be computed an arithmetic circ
uit of size poly(n). In other words\, the complexity class VP (the algeb
raic analog of P) of polynomials\, is closed under taking factors.\nA fund
amental question in this line of research\, which has largely remained ope
n is to understand if other natural classes of multivariate polynomials\,
for instance\, arithmetic formulas\, algebraic branching programs\, consta
nt depth arithmetic circuits or the complexity class VNP (the algebraic an
alog of NP) of polynomials\, are closed under taking factors. In addition
to being fundamental questions on their own\, such 'closure results' for
polynomial factorization play a crucial role in the understanding of hard
ness randomness tradeoffs for algebraic computation.\nI will talk about th
e following two results\, whose study was motivated by these questions.\n1
. The class VNP is closed under taking factors.\nThis proves a conjecture
of Bürgisser.\n2. All factors of degree at most poly(log n) of polynomial
s with constant depth circuits of size\npoly(n) have constant (a slightl
y larger constant) depth arithmetic circuits of size poly(n).\nThis partia
lly answers a question of Shpilka and Yehudayoff and has applications to
hardness-randomness tradeoffs for constant depth arithmetic circuits.\nBa
sed on joint work with Chi-Ning Chou and Noam Solomon.\n
URL:https://www.tcs.tifr.res.in/web/events/932
DTSTART;TZID=Asia/Kolkata:20190107T110000
DTEND;TZID=Asia/Kolkata:20190107T120000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR