Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-037 | 27th March 2019 01:40

Closure of VP under taking factors: a short and simple proof

RSS-Feed




Revision #1
Authors: Chi-Ning Chou, Mrinal Kumar, Noam Solomon
Accepted on: 27th March 2019 01:40
Downloads: 98
Keywords: 


Abstract:

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.



Changes to previous version:

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


Paper:

TR19-037 | 5th March 2019 23:21

Closure of VP under taking factors: a short and simple proof


Abstract:

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.



ISSN 1433-8092 | Imprint