Introduction to geometric complexity theory
Prof. Dr. Markus Bläser, Dr. Christian Ikenmeyer
News
- Last lecture notes update: 2017-Jul-31, 13:20h
- All homework solutions are online.
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 and connections to tensor rank and matrix multiplication have been drawn.
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 and cover some of the recent results.
Time and date
Summer semester 2017,
- Wednesdays 12:15 to 13:45, E1.3, HS 003
- Fridays 12:00 to 13:30, E1.3, HS 003
- Tutorials with Gorav Jindal: Fridays 14:15 to 15:45, E1.3, SR016
Lecturers
- Prof. Dr. Markus Bläser, Email: mblaeser at cs.uni-saarland...
Office Hours: whenever my office door is open, E1 3, room 412
- Dr. Christian Ikenmeyer, Email: cikenmeyer at mpi-inf.mpg.de
Office Hours: whenever my door is open, E1 4, room 311D
Prerequisites
-
"Grundzüge der Theoretischen Informatik" (introduction to theoretical computer science) or equivalent
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.
Minor typos in homework 2 and 7 fixed and a typo in homework 12 fixed.
Lecture Notes
We will keep updating the lecture notes.
Literature
The lecture's topics span a wide range of areas in mathematics. A list of books that is reserved for your studies at the library can be found here:
Literature