21
$\begingroup$

I've read from Wikipedia about Geometric Complexity Theory (GCT) which (if I understood correctly) is a program for coping with the $ P=NP $ problem using algebraic methods.

That program seems promising, but I wonder what the current results of it are.

So what are the current breakthroughs of Geometric Complexity Theory?

$\endgroup$

3 Answers 3

28
$\begingroup$

This is more of a negative result than a positive result and so it may not be what you are looking for, but I consider it a breakthrough: Bürgisser, Ikenmeyer, and Panova showed that a certain very strong form of geometry complexity theory cannot possibly be true. A key idea in geometric complexity theory is to try to separate the orbit closures of the determinant and padded permanent polynomials. A particularly optimistic way one might hope to do this is to show that some irreducible representation of $GL_{n^2}(\mathbb{C})$ occurs in one coordinate ring but does not appear at all in the other. The aforementioned paper proves that this particular hope is overly optimistic.

$\endgroup$
1
  • 3
    $\begingroup$ It's perhaps worth mentioning that at the moment we don't even know how to extend [BIP] from multiplicity zero vs nonzero to multiplicity 1 vs >1, let alone something like "small vs large". $\endgroup$ Sep 5, 2017 at 20:28
19
$\begingroup$

Let $X=(X_{ij})_{1\le i,j\le n}$ be a generic $n\times n$ matrix and $F_1(X)={\rm det}(X)$ the degree $n$ homogeneous polynomial given by the determinant. Let $$ F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right] $$ which takes the permanent of an $m\times m$ submatrix and multiplies by one's favorite linear form in order to make another homogeneous polynomial of degree $n$ (one could also use the entry $X_{11}$ instead of $X_{nn}$). This modification is called padding. Then define the number $$ c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \} $$ where $G$ is $GL(n^2)$ acting on the space $V$ of dimension $n^2$ where $X$ lives and therefore also on the space of degree $n$ polynomial functions of $X$. The $\overline{G\cdot F_i}$ are Zariski closures of orbits. The big conjecture in the area or Valiant's Hypothesis (a complex version of ${\rm P}\neq{\rm NP}$) is that $c(m)$ grows faster than any polynomial in $m$.

Now if $\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$, then one has a surjective $G$-equivariant map $$ \mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d $$ between degree $d$ parts of the coordinate rings of these orbit closures. So the game is to try to show that this does not happen, for $n$ insufficiently large relative to $m$, by proving the existence of a multiplicity obstruction, i.e., an irreducible representation $\lambda$ for which multiplicities satisfy $$ {\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d) $$ or at the level of ideals $$ {\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ . $$

An optimistic approach is to try to show there exist occurrence obstructions, i.e., $\lambda$'s such that ${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$ and ${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$. This hope has been squashed in the work of Bürgisser, Ikenmeyer and Panova mentioned by Timothy. However, the possibility of multiplicity obstructions is still open.

I think the approach by Mulmuley is to try prove the existence of such multiplicity obstructions by leveraging all the tools available from representation theory for the computation of these multiplicities. Personally, I have never been a fan of this approach. Having studied 19th century invariant theory in some depth, it seems more natural to me to approach the orbit separation problem using the explicit tools from that era. This article by Grochow seems to also point in a similar direction (I suspect the third article mentioned by Joseph is in the same vein). In classical language (see Turnbull or Littlewood), one has to explicitly construct a mixed concomitant which vanishes on $F_1$ but not on $F_2$. One also has to do this infinitely often (in $m$) in order to establish the superpolynomial growth property. Such a (degree $d$) concomitant is the same as a specific $G$-equivariant map from your favorite model for the irreducible representation $\lambda$ to ${\rm Sym}^d({\rm Sym}^n(V))$ (Grochow calls that a separating module). Invariant theorists from the 19th century had two methods for generating such objects: elimination theory and diagrammatic algebra.

A very baby example where $F_1$ and $F_2$ are binary quartic forms under the action of $G=SL(2)$ (see this MO question) is say $$ F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4 $$ and $$ F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ . $$ A separating concomitant (here in fact a covariant) is the Hessian of a generic binary quartic $F$ $$ H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ . $$ It vanishes (identically in $x,y$) for $F=F_1$ but not for $F=F_2$. In this case, the Hessian can be seen as an equivariant map form the irreducible given by the second symmetric power (of the fundamental two-dimensional representation) into the coordinate ring for the affine space of binary quartics.

So a possible superoptimistic "plan" for GCT involves the following sequence of steps.

  1. Find a way to generate tons of concomitants.

  2. Identify some explicit candidates for the vanishing on $F_1$ and prove that property.

  3. Show they don't vanish on $F_2$.

Step 1) is in principle solved by the First Fundamental Theorem for $GL(n^2)$ but there is a mismatch: the determinant is a natural object in the invariant theory for $GL(n)\times GL(n)$ (acting on rows and columns) rather than $GL(n^2)$. One could try to repair the mismatch by expressing the basic building block for the invariant theory of $GL(n^2)$ in terms of the one for $GL(n)\times GL(n)$ (see this MO question for a similar reduction problem from $SL(n(n+1)/2)$ to $SL(n)$).

Guessing the right candidates for Step 2) looks hard to me. Knowing beforehand that some multiplicities ${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$ are nonzero would definitely help. Although, one could procrastinate and defer the proof of nonidentical vanishing of the concomitant to Step 3) which should show more than that anyway. If one has such right candidates, showing they vanish on $F_1$ may be easy by arguments one could call Pauli's exclusion principle (contracting symmetrizations with antisymmetrizations), high chromatic number property, or simply "lack of space".

However, I think the most difficult part is Step 3). For example, in my paper "16,051 formulas for Ottaviani's invariant of cubic threefolds" with Ikenmeyer and Royle, the guessing was done by computer search, but with the right candidate in hand, the vanishing on $F_1$ was relatively easy to explain (it's a rather pretty example of chromatic number due to the global properties of the graph rather than some big clique). The analogue of Step 3) in our article was done by brute force computer calculation and we still don't have a clue for why it is true. The paradigmatic problem related to Step 3) is the Alon-Tarsi conjecture (see this MO question and this one too). In my opinion, one needs to make progress on that kind of question (the Four Color Theorem is of this type too, via a reduction due to Kauffman and Bar-Natan) before Valiant's Conjecture.

Since the question is about breakthroughs in GCT. I think this article by Landsberg and Ressayre also deserves some attention since it suggests that a reasonable guess for the exact value of $c(m)$ is $$ \left(\begin{array}{c}2m\\ m \end{array}\right)-1\ . $$ Note that a proof of concept for the explicit "Step 1),2),3) approach", on a much simpler problem, was given by Bürgisser and Ikenmeyer in this article. Finally, for more information on GCT, I highly recommend the review "Geometric complexity theory: an introduction for geometers" by Landsberg.

PS: I should add that my pessimism is specific to the Valiant Hypothesis which is the "Riemann Hypothesis" in the field. Of course, one should not throw the baby with the bath water and denigrate GCT because it so far failed to prove this conjecture. There are plenty of more approachable problems in this area where progress has been made and more progress is expected. See in particular the above-mentioned article by Grochow and review by Landsberg.

$\endgroup$
4
  • $\begingroup$ It's worth noting that the rank of the Hessian is precisely what's used to get the current best lower bound on perm v det, namely $n^2 / 2$ see Mignon-Ressayre, Cai-Chen-Li (comput. complex. 2010) and Landsberg-Manivel-Ressayre. (Also, two small things: you misspelled my name :), and you can link to the final journal version dx.doi.org/10.1007/s00037-015-0103-x since it's open access - it's updated quite a bit from the original arXiv post.) $\endgroup$ Sep 5, 2017 at 20:23
  • 1
    $\begingroup$ Also, even if you are pessimistic about actually resolving Valiant's Conjecture using multiplicity obstructions, studying and learning more about the multiplicities seems like it could still be a useful guide to finding separating modules (that is, it could help you hone in on which isomorphism types of G-modules to be looking for, and therefore what kind of concomitants might possibly be used to separate). $\endgroup$ Sep 5, 2017 at 20:25
  • $\begingroup$ @JoshuaGrochow: Thank you for your comments. Regarding the Valiant Conjecture I would say I am pessimistic across the board as far as methods. As I said in my answer knowing multiplicities for the ideal of the determinant should help narrowing the search for separating modules. Although in the 1,2,3 approach above that's not so essential. One can perhaps graphically construct some concomitant and show it vanishes on the det even though it might actually be identically zero! On can procrastinate as I said and defer showing one actually has a nonzero concomitant to step 3): nonvanishing on perm $\endgroup$ Sep 5, 2017 at 21:01
  • $\begingroup$ @JoshuaGrochow: Oups! You are right I misspelt your name. I hope it's fixed now. Given how often people massacre my name I am certainly sensitized to this issue. My apologies. $\endgroup$ Sep 10, 2017 at 14:57
16
$\begingroup$

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is Ketan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

In the above paper, KM proves that Noether's Normalization Lemma (NNL) is not as intractable as it might seem (from Gröbner basis theory—exponential in $n$). He shows that, "in practice, NNL for explicit varieties can be solved efficiently and correctly with a high probability." The next issue is achieving deterministic polynomial-time. Here he only partially succeeds, showing that "for some interesting cases of explicit varieties," NNL "can indeed be solved deterministically in quasi-poly$(n)$-time." This brings some instances of NNL "from EXPSPACE to quasi-P, assuming the hardness hypothesis for the permanent in geometric complexity theory."

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

$\endgroup$
2
  • 12
    $\begingroup$ It may be worth briefly stating what's in them? $\endgroup$
    – Clement C.
    Jul 28, 2017 at 2:25
  • $\begingroup$ @ClementC.: Attempted on paper (2). $\endgroup$ Aug 2, 2017 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.