Bi-polynomial rank and determinantal complexity.

摘要: The permanent vs. determinant problem is one of the most important problems in theoretical computer science, and main target geometric complexity theory proposed by Mulmuley Sohoni. current best lower bound for determinantal d polynomial d^2/2, due to Mignon Ressayre 2004. Inspired their proof method, we introduce a natural rank concept polynomials, called bi-polynomial rank. related width an arithmetic branching program. homogeneous p even degree 2k defined as minimum n such that can be written summation products polynomials k. We prove gives complexity. As consequence, above improved (d-1)^2 + 1 over field reals. show computation formulated minimization problem. Applying concave technique, reduce lower-bounding proving positive semidefiniteness matrices, this new approach propose computational giving minimization, via techniques minimization. This also yields strategy attack