ECCC-Report TR03-067https://eccc.weizmann.ac.il/report/2003/067Comments and Revisions published for TR03-067en-usTue, 09 Sep 2003 00:51:26 +0300
Paper TR03-067
| Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size |
Ran Raz
https://eccc.weizmann.ac.il/report/2003/067An 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$.
Tue, 09 Sep 2003 00:51:26 +0300https://eccc.weizmann.ac.il/report/2003/067