TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Inhalt des Dokuments

zur Navigation

Leitung

Prof. Dr. Peter Bürgisser

Lupe

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

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

Kontakt

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

eMail
peter.buergisser@offmath.tu-berlin.de

Telefon
+49 (0)30 314 - 75902
Faxgerät
+49 (0)30 314 - 25839

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

Publikationen

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 Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe