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

<p>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.</p>

<hr>

<p>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 <em>padding</em>.
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$.</p>

<p>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 <strong>multiplicity obstruction</strong>, i.e., an irreducible representation $\lambda$ for which multiplicities satisfy
$$
{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)&lt;{\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)&gt;{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ .
$$</p>

<p>An optimistic approach is to try to show there exist <strong>occurrence obstructions</strong>, 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)&gt;0$. This hope has been squashed in the work of B&uuml;rgisser, Ikenmeyer and Panova mentioned by Timothy.
However, the possibility of multiplicity obstructions is still open.</p>

<p>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. <a href="https://arxiv.org/abs/1304.6333" rel="nofollow noreferrer">This article by Gorchow</a> 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 <a href="https://books.google.com/books?id=DbQ-AAAAIAAJ&amp;source=gbs_navlinks_s" rel="nofollow noreferrer">Turnbull</a> or <a href="https://www.jstor.org/stable/91389?seq=1#page_scan_tab_contents" rel="nofollow noreferrer">Littlewood</a>), one has to <strong>explicitly</strong> construct 
a <em>mixed concomitant</em> 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 <em>separating module</em>). Invariant theorists from the 19th century had two methods for generating such objects: elimination theory and <a href="https://mathoverflow.net/questions/168888/who-invented-diagrammatic-algebra">diagrammatic algebra</a>.</p>

<p>A very baby example where $F_1$ and $F_2$ are binary quartic forms under the action of $G=SL(2)$ (see <a href="https://mathoverflow.net/questions/49571/quotient-space-of-mathbbc5-under-the-action-of-sl2-mathbbc">this MO question</a>) 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.</p>

<p>So a possible superoptimistic "plan" for GCT involves the following sequence of steps.</p>

<p>1) Find a way to generate tons of concomitants.</p>

<p>2) Identify some explicit candidates for the vanishing on $F_1$ and prove that property.</p>

<p>3) Show they don't vanish on $F_2$.</p>

<p>Step 1) is in principle solved by the <a href="https://mathoverflow.net/questions/255492/how-to-constructively-combinatorially-prove-schur-weyl-duality">First Fundamental Theorem</a> 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 <a href="https://mathoverflow.net/questions/188746/generalization-of-pascals-theorem-to-higher-dimensions">this MO question</a> for a similar reduction problem from $SL(n(n+1)/2)$ to $SL(n)$).</p>

<p>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'.</p>

<p>However, I think the most difficult part is Step 3). For example, in my paper
<a href="http://www.sciencedirect.com/science/article/pii/S0021869315005657" rel="nofollow noreferrer">"16,051 formulas for Ottaviani's invariant of cubic threefolds"</a> 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 <strong>Alon-Tarsi conjecture</strong> (see <a href="https://mathoverflow.net/questions/56627/symmetric-polynomial-from-graphs">this MO question</a> and <a href="https://mathoverflow.net/questions/259106/explicit-invariant-of-tensors-nonvanishing-on-the-diagonal">this one</a> too). In my opinion, one needs to make progress on that kind of question (the <strong>Four Color Theorem</strong> is of this type too, via a reduction due to Kauffman and Bar-Natan) before Valiant's Conjecture.</p>

<p>Since the question is about breakthroughs in GCT. I think <a href="https://arxiv.org/abs/1508.05788" rel="nofollow noreferrer">this article</a> 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&uuml;rgisser and Ikenmeyer in <a href="http://dl.acm.org/citation.cfm?id=2488627" rel="nofollow noreferrer">this article</a>.
Finally, for more information on GCT, I highly recommend the review
<a href="https://link.springer.com/article/10.1007/s11565-014-0202-7" rel="nofollow noreferrer">"Geometric complexity theory: an introduction for geometers"</a> by Landsberg.</p>

<p><strong>PS:</strong> 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.</p>

CC BY-SA 3.0
2017-09-03T18:00:59.257Z
2017-09-03T18:00:59.257Z
Abdelmalek Abdesselam
<p>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. </p>

<p>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]</p>

<blockquote>
  <p>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? </p>
</blockquote>

<p>[1] <a href="http://blog.computationalcomplexity.org/2008/04/how-to-prove-np-different-from-p.html" rel="nofollow">How to prove NP different than P</a> Fortnow blog</p>

<p>[2] <a href="http://www.cse.buffalo.edu/faculty/regan/papers/pdf/Reg02MSFD.pdf" rel="nofollow">Understanding the Mulmuley-Sohoni Approach to P vs. NP</a> Regan</p>

<p>[3] <a href="http://ramakrishnadas.cs.uchicago.edu/gctexplicit.pdf" rel="nofollow">On P vs. NP and Geometric Complexity Theory</a> Mulmuley</p>

<p>[4] <a href="http://ramakrishnadas.cs.uchicago.edu/gctcacm.pdf" rel="nofollow">The GCT program towards the P vs. NP problem</a> Mulmuley</p>

CC BY-SA 3.0
2013-06-03T21:15:28.633Z
see also [GEOMETRIC COMPLEXITY THEORY: AN INTRODUCTION FOR
GEOMETERS](http://arxiv.org/pdf/1305.7387.pdf) JM Landsberg
vzn
CC BY-SA 3.0
2013-05-14T15:20:15.483Z
2013-05-14T15:20:15.483Z
vzn
<p>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.</p>

<p>Geometric complexity theory proposes to study the <a href="https://en.wikipedia.org/wiki/Computational_complexity_theory">computational complexity</a> of computing functions (say, polynomials) by exploiting the inherent symmetries in complexity and any additional symmetries of the functions being studied. </p>

<p>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}$. </p>

<p>The first key idea (cf. [GCT1, GCT2]) is to use symmetries to organize not the functions themselves, but to organize the (<a href="https://en.wikipedia.org/wiki/Algebraic_geometry">algebro-geometric</a>) properties of these functions, as captured by polynomials such as $p$ above. This enables the use of <a href="https://en.wikipedia.org/wiki/Representation_theory">representation theory</a> 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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Linear_programming">Linear Programming</a> (an algorithm) to prove certain purely combinatorial statements. </p>

<p>Indeed, [GCT6] suggests reducing the representation-theoretic problems above to <a href="http://en.wikipedia.org/wiki/Integer_programming">Integer Programming</a> 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 <a href="http://en.wikipedia.org/wiki/Littlewood%E2%80%93Richardson_rule">Littlewood-Richardson combinatorial rule</a> 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]).</p>

<p>The results of [GCT5] show that explicitly derandomizing <a href="http://en.wikipedia.org/wiki/Noether_normalization_lemma">Noether's Normalization Lemma</a> is essentially equivalent to the notorious open problem in complexity theory of black-box derandomization of <a href="http://en.wikipedia.org/wiki/Polynomial_identity_testing">polynomial identity testing</a>. 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.</p>

<p><strong>Examples of symmetries of complexity and functions</strong></p>

<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Spontaneous_symmetry_breaking">spontaneous symmetry-breaking</a> in physics.) </p>

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

<p>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. </p>

<p>The next problem after Littlewood-Richardson coefficients is the <a href="http://en.wikipedia.org/wiki/Kronecker_coefficient">Kronecker coefficients</a>. 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.</p>

<p>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.</p>

<p><strong>References</strong>
[B] J. Blasiak. <a href="http://arxiv.org/abs/1209.2018">Kronecker coefficients for one hook shape.</a> arXiv:1209.2018, 2012.</p>

<p>[BI] P. Burgisser and C. Ikenmeyer. <a href="http://www.ams.org/mathscinet-getitem?mr=2721518">A max-flow algorithm for positivity of Littlewood-Richardson coefficients.</a> FPSAC 2009.</p>

<p>[BI2] P. Burgisser and C. Ikenmeyer. <a href="http://arxiv.org/abs/1210.8368">Explicit Lower Bounds via Geometric Complexity Theory.</a> arXiv:1210.8368, 2012.</p>

<p>[BZ] A. D. Berenstein and A. V. Zelevinsky. <a href="http://dx.doi.org/10.1023/A:1022429213282">Triple multiplicities for $\mathfrak{sl}(r+1)$ and the spectrum of the exterior algebra of the adjoint representation.</a> J. Algebraic Combin. 1 (1992), no. 1, 7–22. </p>

<p>[GCT1] K. D. Mulmuley and M. Sohoni. <a href="http://dx.doi.org/10.1137/S009753970038715X">Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems.</a> SIAM J. Comput. 31(2), 496–526, 2001.</p>

<p>[GCT2] K. D. Mulmuley and M. Sohoni. <a href="http://dx.doi.org/10.1137/080718115">Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties.</a> SIAM J. Comput., 38(3), 1175–1206, 2008.</p>

<p>[GCT3] K. D. Mulmuley, H. Narayanan, and M. Sohoni. <a href="http://dx.doi.org/10.1007/s10801-011-0325-1">Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient.</a> J. Algebraic Combin. 36 (2012), no. 1, 103–110. </p>

<p>[GCT5] K. D. Mulmuley. <a href="http://arxiv.org/abs/1209.5993">Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's Normalization Lemma.</a> FOCS 2012, also arXiv:1209.5993. </p>

<p>[GCT6] K. D. Mulmuley. <a href="http://ramakrishnadas.cs.uchicago.edu/gct6.pdf">Geometric Complexity Theory VI: the flip via positivity.</a>, Technical Report, Computer Science department, The University of Chicago, January 2011. </p>

<p>[K] S. Kumar. <a href="http://arxiv.org/abs/1109.5996">A Study of the representations supported by the orbit closure of the determinant.</a> arXiv:1109.5996, 2011.</p>

<p>[LO] J. M. Landsberg and G. Ottaviani. <a href="http://arxiv.org/abs/1112.6007">New lower bounds for the border rank of matrix multiplication.</a> arXiv:1112.6007, 2011.</p>

<p>[KT] A. Knutson and T. Tao. <a href="http://dx.doi.org/10.1090/S0894-0347-99-00299-4">The honeycomb model of $\text{GL}_n(\mathbb{C})$ tensor products. I. Proof of the saturation conjecture.</a> J. Amer. Math. Soc. 12 (1999), no. 4, 1055–1090. </p>

<p>[KT2] A. Knutson and T. Tao. <a href="http://www.ams.org/notices/200102/fea-knutson.pdf">Honeycombs and sums of Hermitian matrices.</a> Notices Amer. Math. Soc. 48 (2001), no. 2, 175–186. </p>

CC BY-SA 3.0
2013-05-14T23:14:09.640Z
Re your opening sentence about what level is suitable for Wikipedia: the short answer is as simple as possible, but no simpler. The start of a Wikipedia article, particularly, should be written for as broad an audience as it can be written for (without making a hash of the subject); later parts can become more technical. For more details see the Wikipedia guideline http://en.wikipedia.org/wiki/WP:TECHNICAL (And perhaps it should go without saying that not all articles succeed in these goals.)
David Eppstein
CC BY-SA 3.0
2013-05-15T02:14:49.377Z
A good idea might to aim for a similar level to http://en.wikipedia.org/wiki/Representation_theory which starts out somewhat gently but then gets a lot more technical.
Mugizi Rwebangira
CC BY-SA 3.0
2013-05-16T12:36:59.433Z
I was looking for an explanation understandable by non-experts in CS, who are still scientists in some other field (physics in particular). Your answer fulfills perfectly this requisite. Thanks!
Alessandro Cosentino
CC BY-SA 3.0
2014-10-22T21:33:52.110Z
Why not add this to the Wikipedia page?
mrk
CC BY-SA 3.0
2013-05-14T22:41:44.577Z
2013-05-14T22:41:44.577Z
Joshua Grochow
<p>Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for <a href="http://en.wikipedia.org/wiki/Geometric_Complexity_Theory">a Wikipedia page</a> on the topic (which is stub at the moment). </p>

<p>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.</p>

CC BY-SA 3.0
2013-05-13T19:51:21.837Z
Maybe the answer is to make one :). or at least start it.
Suresh Venkat
CC BY-SA 3.0
2013-05-13T19:58:54.827Z
@SureshVenkat: well, the problem is that I can't come up with something that is suitable for Wikipedia
Alessandro Cosentino
CC BY-SA 3.0
2013-05-13T20:01:22.610Z
Make a stub - you don't have to write the whole thing yourself :).
Suresh Venkat
CC BY-SA 3.0
2013-05-13T21:56:56.430Z
Someone has made a stub after reading this question. It's still a one line explanation. I edited the question to reflect this.
Robin Kothari
CC BY-SA 3.0
2013-05-13T23:38:59.840Z
@Kaveh: of course there is no direct relation between the two fields! In fact Scott even explains in what sense GCT is the string theory of TCS (his is just a meta-argument on how people in the field of theoretical physics and computer science respectively perceive those approaches - of course for totally different questions!). I reported the story just to explain what triggered my question, I didn't mean the two fields are related.
Alessandro Cosentino
CC BY-SA 3.0
2013-05-13T23:41:25.180Z
@Kaveh: Also, I haven't asked anyone to write an article, it's clear from my formulation of the question (see the title itself) that what I want is exactly what you say: an explanation that is understandable by non-experts.
Alessandro Cosentino
CC BY-SA 3.0
2013-05-14T01:04:43.490Z
@Alessandro, I edited the first paragraph to make it more clear what is being asked. I hope that I haven't changed it too much, feel free to roll back or edit. I also replaced [tag:soft-question] with [tag:cc.complexity-theory] as this doesn't seem to be a soft question.
Kaveh
CC BY-SA 3.0
2013-05-14T01:07:49.987Z
Related question: [Mulmuley's GCT program](http://cstheory.stackexchange.com/questions/6959/mulmuleys-gct-program)
Kaveh
CC BY-SA 3.0
2013-05-14T06:53:19.087Z
@AlessandroCosentino: see also the good answer by Joshua to the question "[Prerequisites for learning GCT](http://cstheory.stackexchange.com/questions/15025/prerequisite-for-learning-gct)"
Marzio De Biasi
CC BY-SA 3.0
2013-05-14T14:52:08.647Z
see also [How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?](http://cstheory.stackexchange.com/questions/948/) and [How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?](http://cstheory.stackexchange.com/questions/170/) and [Constructivity in Natural Proof and Geometric Complexity](http://cstheory.stackexchange.com/questions/170/)
vzn
CC BY-SA 3.0
2013-06-03T09:28:27.930Z
It's not a wikipedia-style explanation, but a recent introduction for it was recently published in http://arxiv.org/abs/1305.7387
Alex Grilo
CC BY-SA 3.0
2013-06-03T14:27:23.477Z
Hi @AlexGrilo! An easy survey is also something I was looking for. Thanks!
Alessandro Cosentino
<cc.complexity-theory><gct>
Wikipedia-style explanation of Geometric Complexity Theory
Alessandro Cosentino
# Wikipedia-style explanation of Geometric Complexity Theory

(Asked by: username_0 on 2013-05-13)

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](http://en.wikipedia.org/wiki/Geometric_Complexity_Theory) 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.

**Tags:** cc.complexity-theory, gct

> **Comments:**
> **username_1**: Maybe the answer is to make one :). or at least start it.  
> **username_0**: @SureshVenkat: well, the problem is that I can't come up with something that is suitable for Wikipedia  
> **username_1**: Make a stub - you don't have to write the whole thing yourself :).  
> **username_2**: Someone has made a stub after reading this question. It's still a one line explanation. I edited the question to reflect this.  
> **username_0**: @username_3: of course there is no direct relation between the two fields! In fact Scott even explains in what sense GCT is the string theory of TCS (his is just a meta-argument on how people in the field of theoretical physics and computer science respectively perceive those approaches - of course for totally different questions!). I reported the story just to explain what triggered my question, I didn't mean the two fields are related.  
> **username_0**: @username_3: Also, I haven't asked anyone to write an article, it's clear from my formulation of the question (see the title itself) that what I want is exactly what you say: an explanation that is understandable by non-experts.  
> **username_3**: @Alessandro, I edited the first paragraph to make it more clear what is being asked. I hope that I haven't changed it too much, feel free to roll back or edit. I also replaced [tag:soft-question] with [tag:cc.complexity-theory] as this doesn't seem to be a soft question.  
> **username_3**: Related question: [Mulmuley's GCT program](http://cstheory.stackexchange.com/questions/6959/mulmuleys-gct-program)  
> **username_4**: @AlessandroCosentino: see also the good answer by Joshua to the question "[Prerequisites for learning GCT](http://cstheory.stackexchange.com/questions/15025/prerequisite-for-learning-gct)"  
> **username_5**: see also [How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?](http://cstheory.stackexchange.com/questions/948/) and [How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?](http://cstheory.stackexchange.com/questions/170/) and [Constructivity in Natural Proof and Geometric Complexity](http://cstheory.stackexchange.com/questions/170/)  
> **username_6**: It's not a wikipedia-style explanation, but a recent introduction for it was recently published in http://arxiv.org/abs/1305.7387  
> **username_0**: Hi @AlexGrilo! An easy survey is also something I was looking for. Thanks!  

---

## 3 answers

### Answer by username_8 on 2013-05-14. Score: 40 | Accepted answer

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](https://en.wikipedia.org/wiki/Computational_complexity_theory) 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](https://en.wikipedia.org/wiki/Algebraic_geometry)) properties of these functions, as captured by polynomials such as $p$ above. This enables the use of [representation theory](https://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Linear_programming) (an algorithm) to prove certain purely combinatorial statements.

Indeed, [GCT6] suggests reducing the representation-theoretic problems above to [Integer Programming](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Littlewood%E2%80%93Richardson_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](http://en.wikipedia.org/wiki/Noether_normalization_lemma) is essentially equivalent to the notorious open problem in complexity theory of black-box derandomization of [polynomial identity testing](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Kronecker_coefficient). 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.](http://arxiv.org/abs/1209.2018) arXiv:1209.2018, 2012.

[BI] P. Burgisser and C. Ikenmeyer. [A max-flow algorithm for positivity of Littlewood-Richardson coefficients.](http://www.ams.org/mathscinet-getitem?mr=2721518) FPSAC 2009.

[BI2] P. Burgisser and C. Ikenmeyer. [Explicit Lower Bounds via Geometric Complexity Theory.](http://arxiv.org/abs/1210.8368) 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.](http://dx.doi.org/10.1023/A:1022429213282) 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.](http://dx.doi.org/10.1137/S009753970038715X) 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.](http://dx.doi.org/10.1137/080718115) 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.](http://dx.doi.org/10.1007/s10801-011-0325-1) 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.](http://arxiv.org/abs/1209.5993) FOCS 2012, also arXiv:1209.5993.

[GCT6] K. D. Mulmuley. [Geometric Complexity Theory VI: the flip via positivity.](http://ramakrishnadas.cs.uchicago.edu/gct6.pdf), 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.](http://arxiv.org/abs/1109.5996) arXiv:1109.5996, 2011.

[LO] J. M. Landsberg and G. Ottaviani. [New lower bounds for the border rank of matrix multiplication.](http://arxiv.org/abs/1112.6007) 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.](http://dx.doi.org/10.1090/S0894-0347-99-00299-4) J. Amer. Math. Soc. 12 (1999), no. 4, 1055–1090.

[KT2] A. Knutson and T. Tao. [Honeycombs and sums of Hermitian matrices.](http://www.ams.org/notices/200102/fea-knutson.pdf) Notices Amer. Math. Soc. 48 (2001), no. 2, 175–186.

> **Comments:**
> **username_9**: Re your opening sentence about what level is suitable for Wikipedia: the short answer is as simple as possible, but no simpler. The start of a Wikipedia article, particularly, should be written for as broad an audience as it can be written for (without making a hash of the subject); later parts can become more technical. For more details see the Wikipedia guideline http://en.wikipedia.org/wiki/WP:TECHNICAL (And perhaps it should go without saying that not all articles succeed in these goals.)  
> **username_10**: A good idea might to aim for a similar level to http://en.wikipedia.org/wiki/Representation_theory which starts out somewhat gently but then gets a lot more technical.  
> **username_0**: I was looking for an explanation understandable by non-experts in CS, who are still scientists in some other field (physics in particular). Your answer fulfills perfectly this requisite. Thanks!  
> **username_11**: Why not add this to the Wikipedia page?  

---

### Answer by username_7 on 2017-09-03. Score: 4

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](https://arxiv.org/abs/1304.6333) 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](https://books.google.com/books?id=DbQ-AAAAIAAJ&source=gbs_navlinks_s) or [Littlewood](https://www.jstor.org/stable/91389?seq=1#page_scan_tab_contents)), 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](https://mathoverflow.net/questions/168888/who-invented-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](https://mathoverflow.net/questions/49571/quotient-space-of-mathbbc5-under-the-action-of-sl2-mathbbc)) 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](https://mathoverflow.net/questions/255492/how-to-constructively-combinatorially-prove-schur-weyl-duality) 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](https://mathoverflow.net/questions/188746/generalization-of-pascals-theorem-to-higher-dimensions) 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"](http://www.sciencedirect.com/science/article/pii/S0021869315005657) 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](https://mathoverflow.net/questions/56627/symmetric-polynomial-from-graphs) and [this one](https://mathoverflow.net/questions/259106/explicit-invariant-of-tensors-nonvanishing-on-the-diagonal) 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](https://arxiv.org/abs/1508.05788) 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](http://dl.acm.org/citation.cfm?id=2488627).
Finally, for more information on GCT, I highly recommend the review
["Geometric complexity theory: an introduction for geometers"](https://link.springer.com/article/10.1007/s11565-014-0202-7) 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 by username_5 on 2013-05-14. Score: -5

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](http://blog.computationalcomplexity.org/2008/04/how-to-prove-np-different-from-p.html) Fortnow blog

[2] [Understanding the Mulmuley-Sohoni Approach to P vs. NP](http://www.cse.buffalo.edu/faculty/regan/papers/pdf/Reg02MSFD.pdf) Regan

[3] [On P vs. NP and Geometric Complexity Theory](http://ramakrishnadas.cs.uchicago.edu/gctexplicit.pdf) Mulmuley

[4] [The GCT program towards the P vs. NP problem](http://ramakrishnadas.cs.uchicago.edu/gctcacm.pdf) Mulmuley

> **Comments:**
> **username_5**: see also [GEOMETRIC COMPLEXITY THEORY: AN INTRODUCTION FOR GEOMETERS](http://arxiv.org/pdf/1305.7387.pdf) JM Landsberg  

---

