Geometric Complexity Theory Markus Bläser

News

27.05.2020

Monday, June 01

Since next Monday is a holiday (pentecost) , we will discuss both lectures on Wednesday, June 03. We start at 11:00 (sharp).

22.05.2020

Assignment 3

I changed the wording of the first exercise of Assignment 3, since Julian thinks, the previous wording was misleading.

06.05.2020

Assignment 1

The first assignment is online and can from now on be handed in via the CMS until the 13th of May till the end of the lecture.

Please hand in your solutions as pdf files, either digitally written (preferred, for example with tex) or as a good quality (!) scan of... Read more

The first assignment is online and can from now on be handed in via the CMS until the 13th of May till the end of the lecture.

Please hand in your solutions as pdf files, either digitally written (preferred, for example with tex) or as a good quality (!) scan of a handwritten solution.

26.04.2020

First lecture online

I posted the first lecture. We will discuss it on May 4. There is room for improvement, I am still learning. I even installed chrome on my ubuntu distribution. You can give your comments by email, in the forum or using the feedback feature. We will meet via zoom on... Read more

I posted the first lecture. We will discuss it on May 4. There is room for improvement, I am still learning. I even installed chrome on my ubuntu distribution. You can give your comments by email, in the forum or using the feedback feature. We will meet via zoom on Monday, May 4, at 11:00 am. I will send the link by email.

If you prefer live lectures, I guess that would also be possible. We can discuss this during the first zoom meeting.
 

11.04.2020

Course format

The registration is already open. This allows you to access the lecture notes. You can unregister at any time.

The course will start May 4. I currently assume that the first lectures will be held online. The lecture notes are already available on the web page.... Read more

The registration is already open. This allows you to access the lecture notes. You can unregister at any time.

The course will start May 4. I currently assume that the first lectures will be held online. The lecture notes are already available on the web page. Furthermore, I will pre-record lectures explaining the important things ("flipped classroom"). Every Monday and Wednesday, there will be a short online-session via Zoom  where you can ask questions. (You do not need a Zoom account for this.) The weekly assignments will be given online and you submit your solutions one week later (latex preferred, otherwise submit a scan of your handwritten solutions.) The tutorial will be held via Zoom. The time-slot of the tutorial will be discussed on May 6.

 

Geometric Complexity Theory

 

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. The course bases on an earlier course which I gave together with Christian Ikenmeyer.

 

Time and Date:

I will prerecord the lectures. During  the meetings below, I will briefly summarize the lecture and you can ask questions.

  • Monday 11:00 (sharp) - 12:00, Zoom (see materials section for the link)
  • Wednesday 11:00 (sharp) - 12:00, Zoom (dito)

 

Tutorials:

  • There are weekly tutorials on thursdays 14:15-16:00 via Zoom. The first tutorial will be 14th of May.

 

Assignments:

There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments.

 

Exams:

There will be oral exams at the end of the semester.

 

Prerequisites:

Some knowledge about the P versus NP question is assumed. The core lecture Complexity Theory is helpful, but not mandatory. You should like math!

 

Literature:

Geometric complexity theory is a fairly new field. Therefore, only very little literature is there so far:

  • JM Landsberg - Geometry and complexity theory, Cambridge University Press, 2017
    Free preprint

Mathematical background literature:

  • Bürgisser, Clausen, Shokrollahi - Algebraic Complexity Theory, Springer
  • Northcott - Multilinear Algebra, Cambridge University Press
  • Munkres - Topology, 2nd edition, Pearson
  • Shafarevich - Basic Algebraic Geometry 1: Varieties in Projective Space, Springer
  • Cox, Little, O'Shea - Ideals, Varieties, and Algorithms, 2nd edition, Springer
  • Fulton - Young Tableaux: with applications to representation theory and geometry, Cambridge University Press
  • Kraft - Geometrische Methoden in der Invariantentheorie, Springer (unfortunately only in German)
  • Procesi - Lie Groups: An Approach through Invariants and Representations, Springer
     

 



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators