Abstract:

Arithmetic formulas for computing the determinant and the 
permanent of a matrix have been studied since the 19th century. 
Are there polynomial size formulas for these functions ?
Although the determinant and the permanent are among the most 
extensively studied computational problems, polynomial size 
formulas for these functions are not known. 
An outstanding open problem in complexity theory is to prove 
that polynomial size formulas for these functions do not exist. 
Note, however, that super-polynomial lower bounds for the size 
of arithmetic formulas are not known for any explicit function 
and that questions of this type are considered to be among the 
most challenging open problems in theoretical computer science.
I will talk about a recent solution of this problem for the 
subclass of multi-linear formulas.

An arithmetic formula is multi-linear if the polynomial computed 
by each of its sub-formulas is multi-linear, that is, in each of 
its monomials the power of every input variable is at most one.
Multi-linear formulas are restricted, as they do not allow the
intermediate use of higher powers of variables in order to finally
compute a certain multi-linear function.
Note, however, that for many multi-linear functions, formulas 
that are not multi-linear are very counter-intuitive. Note also 
that both the determinant and the permanent are multi-linear 
functions and that many of the well known formulas for these 
functions are multi-linear formulas.

We prove that any multi-linear arithmetic formula for the 
determinant or the permanent of an $n$ dimensional matrix is 
of size super-polynomial in $n$.
Previous to our result, lower bounds were not known (for any explicit 
function) even for the case of multi-linear formulas of constant depth.