Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DIVISION ELIMINATION:
Reports tagged with Division elimination:
TR21-072 | 23rd May 2021
Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu

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

ISSN 1433-8092 | Imprint