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