University of Wisconsin-Madison UW-Madison Home Page My UW-Madison Search UW
 

 
UW-Madison
Computer Sciences Dept.

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.

 
Theory of Computing | Computer Sciences | UW Home