@article{B-The-Complexity-Of-Factors-Of-Multivariate-Polynomials,
Title = {The Complexity of Factors of Multivariate Polynomials},
Author = {Peter Bürgisser},
Pages = {369-396},
Year = {2004},
Journal = {Foundations of Computational Mathematics},
Volume = {4},
Number = {4},
Note = {There is an erratum for Theorem 5.7, see the Errata section.},
Abstract = {The existence of string functions, which are not polynomial time computable, but whose graph is checkable in polynomial time, is a basic assumption in cryptography. We prove that in the framework of algebraic complexity, there are no such families of polynomial functions of p-bounded degree over fields of characteristic zero. The proof relies on a polynomial upper bound on the approximative complexity of a factor g of a polynomial f in terms of the (approximative) complexity of f and the degree of the factor g. This extends a result by Kaltofen (STOC 1986). The concept of approximative complexity allows to cope with the case that a factor has an exponential multiplicity, by using a perturbation argument. Our result extends to randomized (two-sided error) decision complexity.},
Url = {http://www3.math.tu-berlin.de/algebra/work/comfa.pdf},
Url2 = {http://link.springer.com/article/10.1007/s10208-002-0059-5}
}