#### Milestone Year

### 2003

#### Multilinear Formulas for Permanent and Determinant
require Super-Polynomial Size

The permanent and the determinant of a matrix are among the most
important and most extensively studied polynomials in mathematics.
Mathematical formulas for computing the permanent
and the determinant have been studied since the 19th century.
The smallest known mathematical formula for computing the permanent
is of size exponential in the size of the underlying matrix,
and the smallest known mathematical formula for computing
the determinant is of size super-polynomial in the
size of the underlying matrix. It is widely believed that for
both the permanent and the determinant, there are no formulas of
size polynomial in the size of the underlying matrix, but proving
this conjecture is one of the most central open problems in theoretical
computer science, and is related to the famous P versus NP question.

An interesting subclass of formulas is the class of multilinear
formulas. A formula is called multilinear, if each of its
sub-formulas computes a multilinear polynomial, that is, a
polynomial of degree at most one in each of its input variables.
Multilinear formulas are more intuitive as they do not allow the
intermediate use of higher powers of variables, which finally
cancel each other. Many of the known formulas for computing the
permanent and the determinant are multilinear.
In 2003, a Weizmann scientist proved that for both the permanent
and the determinant, there are no multilinear formulas of size
polynomial in the size of the underlying matrix.