direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

On defining integers and proving arithmetic circuit lower bounds
Citation key B-On-Defining-Integers-And-Proving-Arithmetic-Circuit-Lower-Bounds
Author Peter Bürgisser
Pages 81-103
Year 2009
Journal Computational Complexity
Volume 18
Note Preliminary version in Proc. of STACS 2007, 133-144, February 2007, Aachen
Abstract 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 to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

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