Mrinal Kumar, Rutgers University

Abstract

The determinant complexity of a polynomial P in F[X1, X2, ..., Xn] is the smallest k such that the there is a k*k matrix N, whose entries are linear forms in the X variables, such that P = Determinant(N). The problem of constructing explicit low degree polynomials P such that the determinant complexity of P is at least super-polynomial in n is an important problem in computer science and is closely related to an algebraic analog of the P vs NP question. We will see some very simple proofs of determinant complexity lower bounds for the power sum symmetric polynomials. The bounds obtained are essentially the best lower bound currently known for any explicit polynomial.