direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All Publications

The Complexity of Factors of Multivariate Polynomials
Zitatschlüssel B-The-Complexity-Of-Factors-Of-Multivariate-Polynomials-1
Autor Peter Bürgisser
Buchtitel Proceedings 42nd FOCS
Seiten 378-385
Jahr 2001
Adresse Las Vegas
Monat October 14-17
Zusammenfassung 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.
Link zur Publikation [1] Link zur Originalpublikation [2] Download Bibtex Eintrag [3]
------ Links: ------

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Copyright TU Berlin 2008