32
$\begingroup$

In this guest post by Josh Grochow at the complexity weblog he reports on a recent workshop devoted to GCT that was held at Princeton in July. Several of the attendees argued that we should use GCT to attack easier problems than $\mathsf{P}$ vs. $\mathsf{NP}$ in order to build intuition and see if the method has potential.

The question that has been bugging me:

Is it possible to use GCT to show known separations like $\mathsf{P} \neq \mathsf{EXP}$ or $\mathsf{L} \neq \mathsf{PSPACE}$?

Does something like $\mathsf{L} \neq \mathsf{PSPACE}$

  1. Not even make sense in the GCT context, or
  2. Is utterly trivial and uninteresting in GCT framework, or
  3. Lead to conjectures just as hard as $\mathsf{P}$ vs. $\mathsf{NP}$ ?
$\endgroup$
3
  • $\begingroup$ Josh's comments on that post seem to imply that it IS possible to formulate such separation in "GCT language" but it is non-trivial and no one has got around to doing it yet. But would still appreciate any insight from an expert. $\endgroup$ – Mugizi Rwebangira Sep 4 '10 at 12:15
  • 4
    $\begingroup$ AFAIR, Mulmuley starts his presentation (video.ias.edu/stream&ref=226) with #P vs NC as a more natural question for GCT. This may be a first intuition for answering your question. $\endgroup$ – Michaël Cadilhac Sep 4 '10 at 13:49
  • $\begingroup$ Thanks for that link Michaël. For some reason the volume is too low for me to listen to it on my office desktop, but I will try when I get home. Although in any case Josh has already given a good answer. $\endgroup$ – Mugizi Rwebangira Sep 4 '10 at 19:20
26
$\begingroup$

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.

$\endgroup$
4
  • 9
    $\begingroup$ Seems crazy that it should be so hard to reprove $FP \neq FEXP$! $\endgroup$ – Ryan Williams Sep 4 '10 at 17:04
  • 2
    $\begingroup$ Thank You! That was VERY helpful. My overall idea (and I think that of others as well) was to think of what would be an "easy first step" in this GCT program. But it seems there really isn't one (so far at least). You mentioned that the Grobner Bases approach has a doubly-exponential running time, do you know what was the (asymptotic) running time of the search Burgisser and Ikenmeyer did? $\endgroup$ – Mugizi Rwebangira Sep 4 '10 at 18:59
  • 3
    $\begingroup$ I believe it was still exponential (which partially explains why they couldn't quite reproduce Landsberg's result), but only singly exponential :). $\endgroup$ – Joshua Grochow Sep 4 '10 at 19:07
  • 1
    $\begingroup$ @JoshuaGrochow: It would be helpful if you put an update banner either at the beginning or the end of the answer. In my old age, my eyes aren't what they used to be, and on first skimming the answer, I missed the change. $\endgroup$ – Vijay D Apr 25 '13 at 7:13
14
$\begingroup$

There's a new paper on the arXiv by Joshua Grochow, which shows how to put several known lower bound techniques into the GCT framework and seems like it answers your question somewhat.

(This is mostly just a comment, but no one would notice a comment so I'm posting it as an answer.)

Unifying and generalizing known lower bounds via geometric complexity theory

Joshua A. Grochow

We show that most arithmetic circuit lower bounds and relations between lower bounds naturally fit into the representation-theoretic framework suggested by geometric complexity theory (GCT), including: the partial derivatives technique (Nisan-Wigderson), the results of Razborov and Smolensky on $AC^0[p]$, multilinear formula and circuit size lower bounds (Raz et al.), the degree bound (Strassen, Baur-Strassen), the connected components technique (Ben-Or), depth 3 arithmetic circuit lower bounds over finite fields (Grigoriev-Karpinski), lower bounds on permanent versus determinant (Mignon-Ressayre, Landsberg-Manivel-Ressayre), lower bounds on matrix multiplication (B\"{u}rgisser-Ikenmeyer) (these last two were already known to fit into GCT), the chasms at depth 3 and 4 (Gupta-Kayal-Kamath-Saptharishi; Agrawal-Vinay; Koiran), matrix rigidity (Valiant) and others. That is, the original proofs, with what is often just a little extra work, already provide representation-theoretic obstructions in the sense of GCT for their respective lower bounds. This enables us to expose a new viewpoint on GCT, whereby it is a natural unification and broad generalization of known results. It also shows that the framework of GCT is at least as powerful as known methods, and gives many new proofs-of-concept that GCT can indeed provide significant asymptotic lower bounds. This new viewpoint also opens up the possibility of fruitful two-way interactions between previous results and the new methods of GCT; we provide several concrete suggestions of such interactions. For example, the representation-theoretic viewpoint of GCT naturally provides new properties to consider in the search for new lower bounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.