Geometric Complexity Theory A


Instructor: Ketan Mulmuley
Timings: Thu 4-5.30pm Ry 276

Gives an introduction to an approach to P v/s NP and related lower bound problems through Representation theory and Algebraic Geometry. The course begins with a quick review of Representation theory and Geometric Invariant Theory. After this it gives an overview of GCT. In the next course GCT in covered in more detail.

References:

  • GCT
    • (With M. Sohoni) Geometric complexity theory I: An approach to the P vs. NP and related problems, SIAM J. Comput., vol 31, no. 2, pp. 496-526, (2001). [Download]
    • (With M. Sohoni) Geometric complexity theory, P vs. NP and explicit obstructions, in the proceedings of the International Conference on Algebra and Geometry, Hyderabad, 2001. [Download]
  • Representation Theory
    • Representation Theory: A First Course, by William Fulton and Joe Harris [Buy]
    • Young Tableaux by William Fulton [Buy]
  • Geometric Invariant Theory
    • Lectures on Invariant Theory by Igor Dolgachev [Download]

Lecture Notes

  1. Introduction to Geometric Complexity Theory [Download]
  2. Charecter Theory, Induced Representations [Coming soon]
  3. Representations of S_n and their charecters [Coming soon]
  4. Representations of SL_n and their charecters [Download]
  5. Littlewood-Richardson coefficients [Download]
  6. Kronecker product of Schur Functions with two row shapes - Part I [Download]
  7. Lecture Notes on Geometric Invariant Theory by Milind Sohoni [Download]

Related Links

  • Understanding the Mulmuley-Sohoni approach to P v/s NP [Download]
  • On the Kronecker product of Schur functions of two row shapes [Download]