A quadratic lower bound for the permanent and determinant problem over any characteristic ≠ 2

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 f 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 F[X]. Mignon and Ressayre (2004) [11] 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. Copyright 2008 ACM.