A quadratic bound for the determinant and permanent problem.

International audienceThe determinantal complexity of a polynomial f is defined here as the minimal size of a matrix M with affine entries such that f = det M. This function gives a minoration of the more traditional size of an arithmetical formula. Consider the polynomial "permanent" permd of a d × d matrix with entries Xi,j. A conjecture in complexity theory says that the determinantal complexity (dc) of permd should not be polynomial in d. In this article we prove that dc(permd)> d^2/2, improving the previously known linear minoration. We also begin a systematic study of the function dc, and compute it for the homogeneous polynomials of degree 2