All reports by Author Pranjal Dutta:

__
TR21-072
| 23rd May 2021
__

Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu#### Arithmetic Circuit Complexity of Division and Truncation

Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu

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 ... more >>>