Hilbert functions and geometric complexity theory

Joseph Landsberg
Texas A&M University - College Station

Recently the "method of shifted partial derivatives" (i.e., Hilbert functions of ideals generated by derivatives of a polynomial) has been used by computer scientists to attempt to separate the determinant from the permanent and other related problems. After initial optimism, it was realized that these methods cannot be used to separate the relevant complexity classes. I will discuss a more modest question:
Can these methods be used to improve the state of the art?
This talk will be mostly expository, giving context for the program and presenting basic information about Hilbert functions that should be useful for the workshop. As time permits, I will discuss recent work with K. Efremenko and H. Schenck on the Hilbert functions of the ideals generated by derivatives of the determinant, permanent and "sum-product" polynomials.


View on Youtube

Back to Workshop II: Tools from Algebraic Geometry