Closure of VP under taking factors: a short and simple proof.
2019
In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an $n$ variate degree $d$ polynomial $f$ can be computed by an arithmetic circuit of size $s$, then each of its factors can be computed by an arithmetic circuit of size at most $\textsf{poly}\left(s, n, d\right)$.
However, unlike Kaltofen's argument, our proof does not directly give an efficient algorithm for computing the circuits for the factors of $f$.
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
11
References
0
Citations
NaN
KQI