Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CHI-NING CHOU:
All reports by Author Chi-Ning Chou:

TR19-037 | 5th March 2019
Chi-Ning Chou, Mrinal Kumar, Noam Solomon

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

Revisions: 1

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


TR18-052 | 16th March 2018
Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Some Closure Results for Polynomial Factorization and Applications

In a sequence of fundamental results in the 80's, Kaltofen showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class $VP$ is closed under taking factors. A natural question in this context is to understand if other natural classes of ... more >>>




ISSN 1433-8092 | Imprint