Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

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

ISSN 1433-8092 | Imprint