Wikipedia-style explanation of Geometric Complexity Theory

Question

Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the moment).

Motivation: I am "co-reading" Scott Aaronson's book Quantum Computing since Democritus with a friend of mine who is a researcher in string theory. In the preface of the book, Aaronson calls GCT "the string theory of computer science". Being a string theorist, my friend got excited about this claim and asked me what GCT is. At that point I shamefully realized I didn't have a Wikipedia-ready answer for his question.

Answer 1

I'm not exactly sure what level is suitable for Wikipedia article (different articles seem to be aimed at different levels of expertise) or exactly what you're looking for. So here's a try, but I'm open to feedback.

Geometric complexity theory proposes to study the computational complexity of computing functions (say, polynomials) by exploiting the inherent symmetries in complexity and any additional symmetries of the functions being studied.

As with many previous approaches, the ultimate goal is to separate two complexity classes $\mathcal{C}_{easy}, \mathcal{C}_{hard}$ by showing that there is a polynomial $p$ which takes functions $f$ as inputs (say, by their coefficient vectors) such that $p$ vanishes on every function $f \in \mathcal{C}_{easy}$ but does not vanish on some function $g_{hard} \in \mathcal{C}_{hard}$.

The first key idea (cf. [GCT1, GCT2]) is to use symmetries to organize not the functions themselves, but to organize the (algebro-geometric) properties of these functions, as captured by polynomials such as $p$ above. This enables the use of representation theory in attempting to find such a $p$. Similar ideas relating representation theory and algebraic geometry had been used in algebraic geometry before, but to my knowledge never quite in this way.

The second key idea (cf. [GCT6]) is to find combinatorial (and polynomial-time) algorithms for the resulting representation-theoretic problems, and then reverse-engineer these algorithms to show that such a $p$ exists. This may be taken in the spirit of using Linear Programming (an algorithm) to prove certain purely combinatorial statements.

Indeed, [GCT6] suggests reducing the representation-theoretic problems above to Integer Programming problems, then showing that the resulting IPs are solved by their LP relaxations, and finally giving combinatorial algorithms for the resulting LPs. The conjectures in [GCT6] are themselves motivated by reverse-engineering known results for the Littlewood-Richardson coefficients, an analogous but easier problem in representation theory. In the case of LR coefficients, the Littlewood-Richardson combinatorial rule came first. Later Berenstein and Zelevinsky [BZ] and Knutson and Tao [KT] (see [KT2] for a friendly overview) gave an IP for LR coefficients. Knutson and Tao also proved the saturation conjecture, which implies that the IP is solved by its LP relaxation (cf. [GCT3,BI]).

The results of [GCT5] show that explicitly derandomizing Noether's Normalization Lemma is essentially equivalent to the notorious open problem in complexity theory of black-box derandomization of polynomial identity testing. Roughly how this fits into the larger program is that finding an explicit basis for the functions $p$ that (do not) vanish on $\mathcal{C}_{easy}$ (in this case, the class for which the determinant is complete) could be used to derive a combinatorial rule for the desired problem in representation theory, as has happened in other settings in algebraic geometry. An intermediate step here would be to find a basis for those $p$ that (do not) vanish on the normalization of $\mathcal{C}_{easy}$, which is by construction a nicer algebraic variety -- in other words, to derandomize Noether's Normalization Lemma for DET.

Examples of symmetries of complexity and functions

For example, the complexity of a function $f(x_1, \dotsc, x_n)$ - for most natural notions of complexity - is unchanged if we permute the variables $f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$ by some permutation $\pi$. Thus permutations are symmetries of complexity itself. For some notions of complexity (such as in algebraic circuit complexity) all invertible linear changes of the variables are symmetries.

Individual functions may have additional symmetries. For example, the determinant $\det(X)$ has the symmetries $\det(AXB) = \det(X^{T}) = \det(X)$ for all matrices $A,B$ such that $\det(AB) = 1$. (From what little I picked up about this, I gather that this is analogous to the phenomenon of spontaneous symmetry-breaking in physics.)

Some Recent Progress [this section definitely incomplete and more technical, but a complete account would take tens of pages....I just wanted to highlight some recent progress]

Burgisser and Ikenmeyer [BI2] showed a $\frac{3}{2}n^2$ lower bound on matrix multiplication following the GCT program as far as using representations with zero vs nonzero multiplicities. Landsberg and Ottaviani [LO] gave the best known lower bound of essentially $2n^2$ on the border rank of matrix multiplication using representation theory to organize algebraic properties, but not using representation multiplicities nor combinatorial rules.

The next problem after Littlewood-Richardson coefficients is the Kronecker coefficients. These show up both in a series of problems that is suspected to eventually reach the representation-theoretic problems arising in GCT, and more directly as bounds on the multiplicities in the GCT approach to matrix multiplication and permanent versus determinant. Finding a combinatorial rule for Kronecker coefficients is a long-standing open problem in representation theory; Blasiak [B] recently gave such a combinatorial rule for Kronecker coefficients with one hook shape.

Kumar [K] showed that certain representations appear in the coordinate ring of the determinant with nonzero multiplicity, assuming the column Latin square conjecture (cf. Huang-Rota and Alon-Tarsi; this conjecture also, perhaps not coincidentally, shows up in [BI2]). Hence these representations cannot be used to separate permanent from determinant on the basis of zero vs nonzero multiplicities, though it still might be possible to use them to separate permanent from determinant by a more general inequality between multiplicities.

References [B] J. Blasiak. Kronecker coefficients for one hook shape. arXiv:1209.2018, 2012.

[BI] P. Burgisser and C. Ikenmeyer. A max-flow algorithm for positivity of Littlewood-Richardson coefficients. FPSAC 2009.

[BI2] P. Burgisser and C. Ikenmeyer. Explicit Lower Bounds via Geometric Complexity Theory. arXiv:1210.8368, 2012.

[BZ] A. D. Berenstein and A. V. Zelevinsky. Triple multiplicities for $\mathfrak{sl}(r+1)$ and the spectrum of the exterior algebra of the adjoint representation. J. Algebraic Combin. 1 (1992), no. 1, 7–22.

[GCT1] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput. 31(2), 496–526, 2001.

[GCT2] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. SIAM J. Comput., 38(3), 1175–1206, 2008.

[GCT3] K. D. Mulmuley, H. Narayanan, and M. Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin. 36 (2012), no. 1, 103–110.

[GCT5] K. D. Mulmuley. Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's Normalization Lemma. FOCS 2012, also arXiv:1209.5993.

[GCT6] K. D. Mulmuley. Geometric Complexity Theory VI: the flip via positivity., Technical Report, Computer Science department, The University of Chicago, January 2011.

[K] S. Kumar. A Study of the representations supported by the orbit closure of the determinant. arXiv:1109.5996, 2011.

[LO] J. M. Landsberg and G. Ottaviani. New lower bounds for the border rank of matrix multiplication. arXiv:1112.6007, 2011.

[KT] A. Knutson and T. Tao. The honeycomb model of $\text{GL}_n(\mathbb{C})$ tensor products. I. Proof of the saturation conjecture. J. Amer. Math. Soc. 12 (1999), no. 4, 1055–1090.

[KT2] A. Knutson and T. Tao. Honeycombs and sums of Hermitian matrices. Notices Amer. Math. Soc. 48 (2001), no. 2, 175–186.

Answer 2

I recently gave an answer to a related question on Mathoverflow https://mathoverflow.net/questions/277408/what-are-the-current-breakthroughs-of-geometric-complexity-theory

Since this site is perhaps a better venue, let me simply repeat that answer below. References to Joseph or Timothy are about the other posts for that MO question.

---

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 affine space of dimension $n^2$ where $X$ lives and $\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 Gorchow 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 concomitant is the same as a specific $G$-equivariant map from your favorite model for the irreducible representation $\lambda$ to the polynomial algebra in the $n^2$ variables $X$ (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.

Answer 3

GCT is a research program for proving complexity theory bounds and in a way defies a wikipedia-style abstract/summary due to its heavy abstraction, but for the TCS crowd good surveys are available.[2][3][4] (and surely Wikipedia is the best place for wikipedia entries). it was formulated in the early 2000s by Mulmuley and is both relatively new in complexity theory and very advanced, using and applying advanced mathematics (algebraic geometry) that did not originate in TCS/complexity theory.

the approach is considered promising by some but possibly too complex by other authorities ie it is not proven and therefore controversial whether it could overcome standard known "barriers". (in this sense it does exhibit some signs of a so-called Kuhnian "paradigm shift".) even Mulmuley proposes that it realistically might not succeed (in proving major complexity class separations) after decades of further development. here is a skeptical opinion by Fortnow, a leading authority in the field of complexity theory:[1]

Consider a huge mountain and you want to reach the mountaintop. Ketan comes along and says he'll teach you how to create the tools needed to climb the mountain. It will take a hard month of study and actually these tools aren't good enough to climb the mountain. They need to be improved and these improvements won't happen in your lifetime. But don't you want to learn how others will climb the mountain centuries from now?

[1] How to prove NP different than P Fortnow blog

[2] Understanding the Mulmuley-Sohoni Approach to P vs. NP Regan

[3] On P vs. NP and Geometric Complexity Theory Mulmuley

[4] The GCT program towards the P vs. NP problem Mulmuley