Skip to main content
2 of 2
Added Burgisser-Ikenmeyer new result
Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233

Short answer: probably not (1), definitely not (2), and possibly (3).

This is something I have been thinking about off-and-on for a while now. First, in a sense GCT is really aimed at giving lower bounds on computing functions, rather than decision problems. But your question makes perfect sense for the function class versions of $L$, $P$, $PSPACE$, and $EXP$.

Second, actually proving the boolean versions -- the ones we know and love, like $FP \neq FEXP$ -- is probably incredibly difficult in a GCT approach, since that would require the use of modular representation theory (representation theory over finite fields), which is not well understood in any context.

But a reasonable goal might be to use GCT to prove an algebraic analog of $FP \neq FEXP$.

To get to your question: I believe that these questions can be formulated in a GCT context, though it's not immediately obvious how. More or less, you need a function that is complete for the class and characterized by its symmetries; extra bonus if the representation theory associated to the function is easy to understand, but this latter is usually quite difficult.

Even once the questions are formulated in a GCT context, I have no idea how difficult it will be to use GCT to prove (algebraic analogs of) $FP \neq FEXP$ etc. The representation-theoretic conjectures that will arise in these contexts will likely have a very similar flavor to the ones arising in $P$ vs $NP$ or permanent vs determinant. One might hope that the classical proofs of these separation results might give some idea of how to find the representation-theoretic "obstructions" needed for a GCT proof. However, the proofs of the statements you mention are all hierarchy theorems based on diagonalization, and I do not see how diagonalization will really give you much insight into the representation theory associated with a function that is complete for (the algebraic analog of) $FEXP$, say. On the other hand, I haven't yet seen how to formulate $FEXP$ in a GCT context, so it's a little early to say.

Finally, as I mentioned in that blog post, Peter Burgisser and Christian Ikenmeyer have attempted to re-prove the lower bound on the border-rank of $2 \times 2$ matrix multiplication (which was proven to be 7 in 2006 by Joseph Landsberg). They were able to show the border-rank is at least 6 by a computer search for GCT obstructions. Update April 2013: they have since managed to re-prove Landsberg's result using a GCT obstruction, and to show an asymptotic $\frac{3}{2}n^2 - 2$ lower bound on matrix multiplication using such obstructions. Although GCT has not so far reproduced the known lower bound on matrix multiplication, it does enable a computer search more efficient than the alternative (which would involve Grobner bases, which are doubly-exponential time in the worst case). In their talks at the workshop, both Peter and Christian pointed out (correctly, I'd say) that what we really hope to get of computing small examples is not re-proving known lower bounds, but some insight that will let us use these techniques to prove new lower bounds.

The nice thing about GCT in the context of matrix multiplication is that the technique easily generalizes from $2 \times 2$ to $3 \times 3$ matrix multiplication (although computing the obstructions with the current techniques obviously gets more expensive), whereas Landsberg's approach seems very difficult to implement even for the $3 \times 3$ case. A similar thing could be said about the complexity class separations you mention: GCT is general enough that it may apply not only to known results like $FP \neq FEXP$, but also to unknown ones like $P \neq NP$, whereas we know diagonalization does not.

Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233