direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All 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

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.