Seminar Details
Simple Proofs of Some Determinant Complexity Lower Bounds
- Start Date: January 25, 2017
- Event Start Time: 12:10 PM
- Event End Time: 1:00 PM
- Seminar Series: Graduate Combinatorics Seminar
- Presenter(s): Mrinal Kumar - Rutgers University
- Event Location: Mathematics Graduate Student Lounge -- 7th Floor | Rutgers University | Hill Center | Mathematics Department
- Presentation Type: Stand Alone Presentation
- 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.