Seminars & Colloquia Calendar
Simple proofs of some determinant complexity lower bounds
Location: Hill Grad Student Lounge -
Date & time: Wednesday, 25 January 2017 at 12:10PM - 12:11PM
Mrinal Kumar, Rutgers University 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.
