Geometry and complexity theory

I'm at TAMU today, at the invitation of Piotr Nowak and Ron Douglas. Along with a number of others, they have made significant progress with understanding exactness of groups/property A in terms of appropriate notions of "invariant means" and "vanishing of bounded cohomology". I will probably write about this later.

However, while here I also had a chance to talk with Joseph Landsberg about his preprint P versus NP and geometry. Who could resist such a title? Here is my summary of what he told me. Suppose that you have to compute some huge polynomial in many variables. Then (obviously) in general it will take you a long time. As an example, consider the determinant of an $n\times n$ matrix, which is a polynomial of degree $n$ in $n^2$ variables. A brute force, term-by term evaluation takes a very long time. But in this case there is a trick - Gaussian elimination - which allows one to compute the polynomial much more quickly (with roughly $O(n^4)$ arithmetic operations I think). This is a hidden symmetry leading to speedy computation. Other polynomials, e.g. most famously the permanent (which is the same as the determinant but with all signs $+$), cannot (so far as is known) be computed in this easy way.

This leads to the notion of determinantal complexity (Valiant). You can envisage computing some polynomial such as the permanent of an $n\times n$ matrix by computing instead the determinant of some larger matrix built out of the original one in some way. (If the "larger matrix" is allowed to be sufficiently much larger one can always do this.) Define the determinantal complexity of the (sequence of) given polynomials to be the function that tells you how much you must increase the size of an $n\times n$ matrix to build a larger matrix that computes your polynomial via a determinat. Valiant conjectured that for the permanent, the determinantal compelxity grows faster than any polynomial. If I understand correctly, the falsity of this conjecture (i.e. a polynomial bound for $dc$ of the permanent) would imply $P=NP$.

To address this, the program of "geometric complexity theory" transfers the problem to one in algebraic or differential geometry. One looks at the variety defined by the determinant (in projective space) and allows the general (or special) linear group of the $n^2$ coordinates to act. The permanent (in some smaller degree $d$) defines a point in this space and the question becomes whether this point (or the Zariski closure of its orbit) lies in the Zariski closure of the orbit of the determinant. This question is then addressed either by representation theory (the ring of regular functions on a $G$-orbit can be completely described in terms of representation theory) or by local differential geometry.