Given 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 computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen'87 & WACT'16). This result is an exponential improvement over Strassen's classic 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 this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions 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.
This 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/ .
Zoom Link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
