On defining integers and proving arithmetic circuit lower bounds
Peter Buergisser University of Paderborn
Friday, April 27, 2007 11:00 a.m., 2310 CS
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 $rod {k=1}^n (X-k)$ and the Taylor approximations $ {k=0}^n ac1{k!} X^k$ and $ {k=1}^n ac1{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.
|