TU Berlin

Fachgebiet Algorithmische AlgebraJournal Publications

Inhalt des Dokuments

zur Navigation

Journal Publications

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



Schnellnavigation zur Seite über Nummerneingabe