Seminars & Colloquia Calendar

Download as iCal file

Graduate Student Combinatorics Seminar Sponsored by DIMACS

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.