Revision #1 Authors: Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Accepted on: 27th March 2019 01:40

Downloads: 656

Keywords:

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 poly(s, n, d).

However, unlike Kaltofen's argument, our proof does not directly give an efficient algorithm for computing the circuits for the factors of f.

A few typos, and a clarification in the proof of Lem 1.2.

TR19-037 Authors: Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Publication: 6th March 2019 07:52

Downloads: 738

Keywords:

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 poly(s, n, d).

However, unlike Kaltofen's argument, our proof does not directly give an efficient algorithm for computing the circuits for the factors of f.