Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-113 | 25th August 2006 00:00

On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity

RSS-Feed




TR06-113
Authors: Peter Buergisser
Publication: 5th September 2006 02:43
Downloads: 1292
Keywords: 


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$ by $n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $\log 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 \frac1{k!} X^k$ and $\sum_{k=1}^n \frac1{k} X^k$ of exp and log, respectively, can be computed by arithmetic circuits of size polynomial in $\log n$ (allowing divisions). This connects several so far unrelated conjectures in algebraic complexity.



ISSN 1433-8092 | Imprint