direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content


Prof. Dr. Peter Bürgisser


Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Raum MA 317 (3. OG)
Institut für Mathematik


Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771


+49 (0)30 314 - 75902
+49 (0)30 314 - 25839

Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.


The Complexity of Factors of Multivariate Polynomials (Erratum)
Citation key B-Erratum-The-Complexity-of-Factors-of-Multivariate-Polynomials
Author Peter Bürgisser
Year 2018
DOI 10.1007/s10208-002-0059-5
Month 12
Note This is an updated version of a paper published in J. FoCM in 2004. Here we have corrected an error in the statement and proof of Theorem 5.7.
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 polynomially 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 to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.