ECCC-Report TR21-072https://eccc.weizmann.ac.il/report/2021/072Comments and Revisions published for TR21-072en-usMon, 24 May 2021 16:20:40 +0300
Paper TR21-072
| Arithmetic Circuit Complexity of Division and Truncation |
Gorav Jindal,
Pranjal Dutta,
Anurag Pandey,
Amit Sinhababu
https://eccc.weizmann.ac.il/report/2021/072 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.
Mon, 24 May 2021 16:20:40 +0300https://eccc.weizmann.ac.il/report/2021/072