A first introduction to geometric complexity theory
Dr. Christian Ikenmeyer
News
- A new version of the lecture notes is available: 2018-July-25, 12:40h
Course description
Geometric complexity theory is an ambitious program initiated in 2001 by Mulmuley and Sohoni towards solving the famous P vs NP problem. The idea is to use algebraic geometry and representation theory to prove complexity lower bounds for explicit problems. There has been a significant amount of research activity in this direction during the last few years.
In this course we will give short introductions to algebraic complexity theory, to basic algebraic geometry, and to classical representation theory. The goal is to give a first introduction to geometric complexity theory.
Time and date
Summer semester 2018,
- Wednesdays 12:15-13:45, Room 024 in E1 4, Max-Planck-Institut für Informatik.
- weekly Tutorials with Anurag Pandey: Fridays 14:15-15:45, Room 023 in E1 4, Max-Planck-Institut für Informatik.
Lecturers
- Dr. Christian Ikenmeyer, Email: cikenmeyer at mpi-inf.mpg.de
Office Hours: whenever my door is open, E1 4, room 311D
Prerequisites
-
"Mathematik für Informatiker II" or "Lineare Algebra I" or equivalent is mandatory.
-
"Mathematik für Informatiker I" or "Analysis I" or equivalent is helpful.
-
"Grundzüge der Theoretischen Informatik" (introduction to theoretical computer science) or equivalent is helpful.
-
This lecture covers a subset of the material from the 2017 summer semester lecture "Introduction to geometric complexity theory", so you cannot obtain credits if you already passed that lecture.
- I recommend attending the lecture "Complexity Theory" by Professor Markus Bläser in parallel, which provides a broader perspective on complexity theory.
Grading
There will be oral exams at the end of the semenster (several dates are available).
Assignments
There will be weekly assignments. You need to obtain half of the points to be admitted to the exam.
Literature
We follow subsets of last year's lecture notes.
The library has a "Semesterapparat" for this lecture, where several books are available that can be used as additional resources.