ECCC-Report TR19-037https://eccc.weizmann.ac.il/report/2019/037Comments and Revisions published for TR19-037en-usWed, 27 Mar 2019 01:40:26 +0200
Revision 1
| Closure of VP under taking factors: a short and simple proof |
Mrinal Kumar,
Chi-Ning Chou,
Noam Solomon
https://eccc.weizmann.ac.il/report/2019/037#revision1In 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.
Wed, 27 Mar 2019 01:40:26 +0200https://eccc.weizmann.ac.il/report/2019/037#revision1
Paper TR19-037
| Closure of VP under taking factors: a short and simple proof |
Mrinal Kumar,
Chi-Ning Chou,
Noam Solomon
https://eccc.weizmann.ac.il/report/2019/037In 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.
Wed, 06 Mar 2019 07:52:21 +0200https://eccc.weizmann.ac.il/report/2019/037