__
TR03-067 | 14th August 2003 00:00
__

#### Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size

TR03-067
Authors:

Ran Raz
Publication: 9th September 2003 00:51

Downloads: 4249

Keywords:

**Abstract:**
An arithmetic formula is multi-linear if the polynomial computed

by each of its sub-formulas is multi-linear. We prove that any

multi-linear arithmetic formula for the permanent or the

determinant of an $n \times n$ matrix is of size super-polynomial

in $n$.