All reports by Author Peter Buergisser:

__
TR06-113
| 25th August 2006
__

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

Peter Buergisser

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 ... more >>>