The 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.
@article{hal-00818200,
author = {Mignon, Thierry and Nicolas, Ressayre},
title = {A quadratic bound for the determinant and permanent problem.},
journal = {HAL},
volume = {2004},
number = {0},
year = {2004},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00818200}
}
Mignon, Thierry; Nicolas, Ressayre. A quadratic bound for the determinant and permanent problem.. HAL, Tome 2004 (2004) no. 0, . http://gdmltest.u-ga.fr/item/hal-00818200/