Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-072 | 23rd May 2021 22:22

Arithmetic Circuit Complexity of Division and Truncation



Given polynomials $f,g,h\,\in \mathbb{F}[x_1,\ldots,x_n]$ 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). The 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))$.

Further, we show that any univariate polynomial family $(f_d)_d$, defined by the initial segment of the power series expansion of rational function $g_d(x)/h_d(x)$ up to degree $d$ (i.e.~$f_d = g_d/h_d \bmod x^{d+1}$), where circuit size of $g$ is $s_d$ and degree of $g_d$ is at most $d$, can be computed by a circuit of size $\poly(s_d,\deg(h_d),\log d)$.
We also show a hardness result when the degrees of the rational functions are high (i.e.~$\Omega (d)$), assuming hardness of the integer factorization problem.

ISSN 1433-8092 | Imprint