Quadratic lower bound for permanent Vs. Determinant in any characteristic

Abstract

In Valiant's theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (xij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of xij 's, and the equality is in [X]. Mignon and Ressayre (2004) proved a quadratic lower bound m = Ω(n2) for fields of characteristic 0. We extend the Mignon-Ressayre quadratic lower bound to all fields of characteristic ≠ 2. © 2010 Birkhäuser/Springer Basel.