Seminar:

Spring, Thursdays, Blocker 506A, 4:00-4:50 PM


Date: April 6

"  Algebra, Geometry and Complexity: How hard is it to compute polynomials? "
  Fulvio Gesmundo  

Abstract

Algebraic complexity theory studies problems in complexity theory that can be phrased in terms of polynomial evaluation. The goal of this seminar is to give an overview on the flagship conjecture stating that it is not possible to write the permanent polynomial of degree m as a specialization of the determinant polynomial of degree n if n grows at most polynomially in m - this is the algebraic version of the famous P vs NP conjecture in complexity theory. We discuss some features of this problem, the role of algebraic geometry and some recent results.