BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1380
DTSTAMP:20240104T091221Z
SUMMARY:Deterministic Algorithms for Low-Degree Factors of Constant-Depth C
ircuits
DESCRIPTION:Speaker: Varun Ramanathan (TIFR)\n\nAbstract: \nFor every const
ant d\, we design a subexponential time deterministic algorithm that takes
as input a multivariate polynomial f given as a constant depth algebraic
circuit over the field of rational numbers\, and outputs all irreducible f
actors of f of degree at most d together with their respective multiplicit
ies. Moreover\, if f is a sparse polynomial\, then the algorithm runs in q
uasipolynomial time. Our results are based on a more fine-grained connecti
on between polynomial identity testing (PIT) and polynomial factorization
in the context of constant degree factors and rely on a clean connection b
etween divisibility testing of polynomials and PIT due to Forbes and on su
bexponential time deterministic PIT algorithms for constant depth algebrai
c circuits from the recent work of Limaye\, Srinivasan and Tavenas.\nThis
will be a conference-style short talk of about 20 minutes\, with questions
in the end.\n
URL:https://www.tcs.tifr.res.in/web/events/1380
DTSTART;TZID=Asia/Kolkata:20240105T160000
DTEND;TZID=Asia/Kolkata:20240105T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR