ECCC-Report TR06-113https://eccc.weizmann.ac.il/report/2006/113Comments and Revisions published for TR06-113en-usTue, 05 Sep 2006 02:43:38 +0300
Paper TR06-113
| On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity |
Peter Buergisser
https://eccc.weizmann.ac.il/report/2006/113Let $\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.
Tue, 05 Sep 2006 02:43:38 +0300https://eccc.weizmann.ac.il/report/2006/113