BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Given n-variate polynomials f\,g\,h such that f=g/h\, where bo
th g and h are computable by arithmetic circuits of size s\, we show that f
can be computed by a circuit of size poly(s\, deg(h)). This solves a speci
al case of division elimination for high-degree circuits (Kaltofen’87 &\
; WACT’16). This result is an exponential improvement over Strassen’s class
ic result (Strassen’73) when deg(h) is poly(s) and deg(f) is exp(s)\, since
the latter gives an upper bound of poly(s\, deg(f)). The second part of t
his work deals with the complexity of computing the truncations of uni-vari
ate polynomials or power series. We first show that the truncations of rati
onal functions are easy to compute. We also prove that the truncations of
even very simple algebraic functions are hard to compute\,unless integer fa
ctoring is easy. This is a joint work with Pranjal Dutta\, Anurag Pande
y and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.
il/report/2021/072/ .
DTSTAMP:20210607T160200
DTSTART:20210628T160000
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Gorav Jindal (Technische Universität Berlin): Arithmetic Circuit Co
mplexity of Division and Truncation
UID:107918331@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20210628-C-Jindal.html
END:VEVENT
END:VCALENDAR