It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory.

While I am a CS student and do NOT have classes of very abstract and pure mathematics, I am interested in this program.

Is there a list of "minimum knowledge" for learning this theory ?

This list includes lecture notes of CS or math departments, surveys of any journal or conferences, and text books of pure math.

[EDIT: Added later] Thank you for your comments.

General theory of computing: I read Sipser's book with the title "Introduction to the Theory of Computation"

Complexity Theory :In particular, I am interested in concrete models for lower bounds of complexity. Thus I read the part of the "concrete lower bounds" in Arora-Barak's text book. I also have basic knowlede in the several chapers of the communication complexity book written by Nisan.

Basic Mathematics : I have learnt about proof-based linear algebra such as general definition of the vector space etc and precicely argument of calculas based on epsilon-delta argument.

Algebra: I have learned about definition and examples of group, ring, and field. I had a class for cs students, and have not learned about general thoery of this algebraic systems.

  • 3
    $\begingroup$ it would help if you stated more precisely how much complexity theory, linear algebra, algebra, you know. You should also state your goal. Requirements for a general, high-level picture are different from doing a project in the area. $\endgroup$
    – Vijay D
    Jan 9 '13 at 7:16
  • 1
    $\begingroup$ See cstheory.stackexchange.com/questions/6959/mulmuleys-gct-program $\endgroup$
    – Vijay D
    Jan 9 '13 at 7:17
  • 1
    $\begingroup$ and cstheory.stackexchange.com/a/14978/4155 $\endgroup$
    – Vijay D
    Jan 9 '13 at 7:18
  • $\begingroup$ Try some graduate algebra first, especially commutative algebra. $\endgroup$
    – Zeyu
    Jan 9 '13 at 9:07

The short answer: the really minimum knowledge of math to understand the first half of the plan of GCT, once you've seen a little of groups, rings, and fields, is basically laid out in Chapter 3 of my thesis (shameless self plug). That chapter is, however, incomplete, in that I don't get to the representation theory part of things. The representation theory is crucial for the second half of the plan (which is why I'm working on extending that chapter to include it).

If you really want to get into GCT, Symmetry, Representations, and Invariants by Goodman and Wallach and Actions and Invariants of Algebraic Groups by W. Ferrers Santos are both relatively self-contained and have lots of good information that is pertinent to GCT. I'm not sure if they're the best sources to learn from, as I only learned about them after I had learned much of this material, but they are good in terms of the ratio of what they cover to what's relevant to GCT. Fulton and Harris is great for representation theory and lots of the examples/exercises in the book are relevant to GCT.

The longer answer: it really depends on what/how much you want to learn about GCT, as Vijay pointed out. The topics below are just what I think is the background needed, since that was the question. I'm not sure this is a complete list - I would recommend trying to read some of the papers on GCT, and when you get lost go look for background material. As you're learning the background material, every so often come back to the GCT papers and see if you can follow further.

(Depending on what you want to learn, I would actually disagree with Zeyu that you should try some graduate commutative algebra first, though at some point in learning GCT this will become necessary.)

If you want to understand, for example, Mulmuley's recent FOCS paper, you'll want to understand:

  • the hardness vs. randomness principle (see Impagliazzo--Kabanets, and also perhaps Bill Gasarch's list of papers on hardness v randomness)
  • basic algebraic geometry up to Hilbert's Nullstellensatz and Noether's Normalization Lemma. These can be found in any basic textbook on algebraic geometry and probably in most lecture notes on it.
  • some classical invariant theory (you don't really need geoemtric invariant theory, schemes and the Mumford-Fogarty-Kirwan book for this paper). Sturmfels' book Algorithms in Invariant Theory comes to mind.
  • For certain results in the paper, but by no means for the paper in general, you might want some of (and these references can also be found in the paper): representation theory of $SL_n$ as in Fulton and Harris, results on matrix invariants [Artin, Procesi, Razymslov], ...

If you want to understand the general outline of the GCT approach but in some mathematical detail, I'd suggest:

  • The permanent versus determinant problem. #P-completeness of permanent and GapL-completeness of determinant. Agrawal has a good survey (only very slightly outdated) on this, and the proofs of completeness can be found in Burgisser's book Completeness and Reductions in Algebraic Complexity Theory.

  • Groups and group actions (algebraic groups and algebraic group actions are helpful, but not necessary at this level). You should understand the Orbit-Stabilizer Theorem.

  • Affine algebraic geometry through Hilbert's Nullstellensatz. Basically you just need to understand the correspondence between affine algebraic varieties and their coordinate rings.

  • Basic representation theory of $GL_n$ as in Fulton and Harris. Aside from basic definitions, you need to know complete reducibility of these representations, and the fact that representations of $GL_n$ are classified by partitions, but you don't necessarily need to know the proof/constructions of the latter.

If you want to understand deeply what's going on (and I'm not sure I can claim to be there yet, but I think I know what I need to know to get there), you should probably also understand:

  • The structure of reductive algebraic groups and orbit closures in their representations. I like the book by W. Ferrers Santos for this, but also Linear Algebraic Groups by Borel, The Classical Groups by Weyl, and other classics.

  • The Luna-Vust machinery (Luna's Slice Theorem, Luna-Vust complexity)

  • Tannakian Duality (see the paper by Deligne--Milne; this will be tough reading without some background in category theory and affine algebraic groups). This essentially says that "(pro-)affine algebraic groups are determined by their representations." I don't think you need the whole paper, so much as how to recover a group from its category of representations (Cor. 3.4).

  • More representation theory, especially as applied to the coordinate rings of algebraic groups and their orbit closures. I really like the book by Goodman and Wallach for this, particularly because it's basically self-contained, and it has a lot of exactly what you need to understand GCT. (Also, many of the expository/side sections and exercises in Fulton and Harris are right on the mark for GCT, especially those about Littlewood-Richardson and Kronecker coefficients.)

If you want to actually work on the representation theory, you probably want to understand more algebraic combinatorics / combinatorial representation theory. I don't really know all the right references for this, but certainly understanding the Littlewood-Richardson rule is a must, and Fulton's book Young Tableaux is good for this.

The most recent papers on this side of things that I know of are Blasiak, Kumar, and Bowman, De Visscher, and Orellana.

Depending on what direction you want to go in, you may also want to look into quantum groups, though this isn't necessarily necessary (note: these are not a special case of groups, but rather a generalization in a certain direction).

On the more geometric side of things, you'll want to look into things like differential geometry for tangent and osculating spaces, curvature, dual varieties, and the like, which are underlying the best known lower bound on perm vs. det due to Mignon--Ressayre and followed by Landsberg--Manivel--Ressayre. (Mignon--Ressayre can be understood without any of these things, but you can view their paper loosely as studying the curvature of certain varieties; for a less loose view, see the use of dual varieties in Landsberg--Manivel--Ressayre.) (See also Cai, Chen, and Li, which extends Mignon--Ressayre to all odd characteristics.) See also Landsberg and Kadish.

If you're interested in the GCT approach to matrix multiplication, it's all about tensor rank, border rank, and secant varieties. I'd suggest looking at the papers by Burgisser--Ikenmeyer, Landsberg and Ottaviani, Landsberg, Landsberg's survey and book. Of course, it would also be good to know the classical stuff on matrix multiplication (both upper and lower bounds), but that's a whole separate can of worms.

  • 1
    $\begingroup$ +1 ps: it would be great if you can also add links to the papers and books in your answer. $\endgroup$
    – Kaveh
    Jan 10 '13 at 6:34
  • 1
    $\begingroup$ Is the general theory of topology needed ? $\endgroup$
    – syucha
    Jan 10 '13 at 6:41
  • 4
    $\begingroup$ I feel like all of cstheory unanimously deferred to you on this one. Great answer. If you marked the "If you want" parts more prominently, the structure of your answer would be more visually evident. $\endgroup$
    – Vijay D
    Jan 10 '13 at 9:06
  • 6
    $\begingroup$ Josh is our local expert :) $\endgroup$ Jan 10 '13 at 17:43
  • 2
    $\begingroup$ @syucha: Depending on what you mean by "general theory of topology," say as typically taught in an undergrad topology course, NO. You don't need to know about most of point-set topology. That being said, understanding the basics of topology is useful (and necessary-ish) for understanding algebraic geometry (cf. the Zariski topology) and differential geometry (for which you really just need topology of manifolds, not general point-set topology). Deeper things from topology, like sheaves and vector bundles, are useful for some of the deeper stuff in GCT. $\endgroup$ Jan 14 '13 at 22:25

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.