@ARTICLE{B-The-Complexity-Of-Factors-Of-Multivariate-Polynomials,
 JOURNAL={Foundations of Computational Mathematics},
 TITLE={The Complexity of Factors of Multivariate Polynomials},
 VOLUME={4},
 AUTHOR={Peter Bürgisser},
 YEAR={2004},
 URL={http://www3.math.tu-berlin.de/algebra/work/comfa.pdf},
 PAGES={369-396},
 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.},
 URL2={http://link.springer.com/article/10.1007/s10208-002-0059-5},
 NUMBER={4}
}

{"_id":"Jqsdm7ScQ8jaxWfJv","bibbaseid":"brgisser-thecomplexityoffactorsofmultivariatepolynomials-2004","downloads":0,"creationDate":"2017-01-04T12:11:10.518Z","title":"The Complexity of Factors of Multivariate Polynomials","author_short":["Bürgisser, P."],"year":2004,"bibtype":"article","biburl":"http://www3.math.tu-berlin.de/algebra/static/papers.parsed.bib","bibdata":{"bibtype":"article","type":"article","journal":"Foundations of Computational Mathematics","title":"The Complexity of Factors of Multivariate Polynomials","volume":"4","author":[{"firstnames":["Peter"],"propositions":[],"lastnames":["Bürgisser"],"suffixes":[]}],"year":"2004","url":"http://www3.math.tu-berlin.de/algebra/work/comfa.pdf","pages":"369-396","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.","url2":"http://link.springer.com/article/10.1007/s10208-002-0059-5","number":"4","bibtex":"@ARTICLE{B-The-Complexity-Of-Factors-Of-Multivariate-Polynomials,\r\n JOURNAL={Foundations of Computational Mathematics},\r\n TITLE={The Complexity of Factors of Multivariate Polynomials},\r\n VOLUME={4},\r\n AUTHOR={Peter Bürgisser},\r\n YEAR={2004},\r\n URL={http://www3.math.tu-berlin.de/algebra/work/comfa.pdf},\r\n PAGES={369-396},\r\n 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.},\r\n URL2={http://link.springer.com/article/10.1007/s10208-002-0059-5},\r\n NUMBER={4}\r\n}\r\n\r\n","author_short":["Bürgisser, P."],"key":"B-The-Complexity-Of-Factors-Of-Multivariate-Polynomials","id":"B-The-Complexity-Of-Factors-Of-Multivariate-Polynomials","bibbaseid":"brgisser-thecomplexityoffactorsofmultivariatepolynomials-2004","role":"author","urls":{"2":"http://link.springer.com/article/10.1007/s10208-002-0059-5","Paper":"http://www3.math.tu-berlin.de/algebra/work/comfa.pdf"},"downloads":0,"html":""},"search_terms":["complexity","factors","multivariate","polynomials","bürgisser"],"keywords":[],"authorIDs":[],"dataSources":["mFLw2PzriqAWWFuqX"]}