BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1135
DTSTAMP:20230914T125951Z
SUMMARY:Arithmetic Circuit Complexity of Division and Truncation
DESCRIPTION:Speaker: Gorav Jindal (TU Berlin\, Germany.)\n\nAbstract: \nGiv
en n-variate polynomials f\,g\,h such that f=g/h\, where both g and h are
computable by arithmetic circuits of size s\, we show that f can be comput
ed by a circuit of size poly(s\, deg(h)). This solves a special case of di
vision elimination for high-degree circuits (Kaltofen'87 & WACT'16). This
result is an exponential improvement over Strassen's classic result (Stras
sen'73) when deg(h) is poly(s) and deg(f) is exp(s)\, since the latter giv
es an upper bound of poly(s\, deg(f)).\nThe second part of this work deals
with the complexity of computing the truncations of uni-variate polynomia
ls or power series. We first show that the truncations of rational functio
ns are easy to compute. We also prove that the truncations of even very
simple algebraic functions are hard to compute\, unless integer factoring
is easy.\nThis is a joint work with Pranjal Dutta\, Anurag Pandey and Amit
Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report
/2021/072/ .\nZoom Link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlp
ZWmhNYTJGQTF6Zz09\n \n
URL:https://www.tcs.tifr.res.in/web/events/1135
DTSTART;TZID=Asia/Kolkata:20210611T171500
DTEND;TZID=Asia/Kolkata:20210611T181500
END:VEVENT
END:VCALENDAR