Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-067 | 14th August 2003 00:00

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

RSS-Feed




TR03-067
Authors: Ran Raz
Publication: 9th September 2003 00:51
Downloads: 1888
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