CS 782: An Introduction to
Geometric Complexity Theory.
The course aims to introduce Geometric Complexity Theory
(GCT),
a particular approach to understanding computational
complexity, along with the algebraic and geometric tools
needed. Prerequisites are a familiarity and facility with
basic group theory, linear alegbra and
commutative algebra and some rudimentary notions of ideals
and varieties. Most of this is obtained through a
semester long course on algebra, using say,
Artin's book "Algebra".
This exposure is
essential. Most of this will be reviewed through
examples which lie on the GCT path.
We will use some standard books: Humphreys, for
Algebraic Groups, Harris for Algebraic Geometry and others
as and when needed. These are NOT prerequisites. We will
also be reading research papers.
The class will meet twice a week, for the initial few weeks.
Familiarity required: Linear Algebra, Basic Algebra,
Commutative algebra, Groups
and group actions, group representation, ideals and varieties. Artin's Algebra
pdf (Chapters
1-4, 8.1-8.4, 9-11) is adequate.
Detailed Course contents pdf
Lecture topics and notes pdf
Practice problems from Artin: You should be familiar with most problems at the end of
chapters 1-4. We will discuss on friday.
Some reference books:
Kunze, Algebraic Geometry and Commutative Algebra pdf
Sturmfels, Algorithms in Invariant Theory pdf
yy Humphreys, Algebraic Groups pdf
Harris, Algebraic Geometry pdf
Derksen, Constructive Invariant Theory pdf