Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with factorials:
TR06-113 | 25th August 2006
Peter Buergisser

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

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

ISSN 1433-8092 | Imprint