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

On defining integers and proving arithmetic circuit lower bounds
Zitatschlüssel B-On-Defining-Integers-And-Proving-Arithmetic-Circuit-Lower-Bounds
Autor Peter Bürgisser
Seiten 81-103
Jahr 2009
Journal Computational Complexity
Jahrgang 18
Notiz Preliminary version in Proc. of STACS 2007, 133-144, February 2007, Aachen
Zusammenfassung Let $\tau(n)$ denote the minimum number of arithmetic operations sufficient to build the integer $n$ from the constant $1$. We prove that if there are arithmetic circuits for computing the permanent of $n× n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $łog n$. Under the same assumption on the permanent, we conclude that the Pochhammer-Wilkinson polynomials $\prod_k=1^n (X-k)$ and the Taylor approximations $\sum_k=0^n \frac1k! X^k$ and $\sum_k=1^n \frac1k X^k$ of $\exp$ and $łog$, respectively, can be computed by arithmetic circuits of size polynomial in $łog n$ (allowing divisions). This connects several so far unrelated conjectures in algebraic complexity.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe