News
No lecture on Dec 9.Written on 08.12.21 by Markus Bläser There will be no lecture tomorrow. There will be an extra tutorial next week tba. |
Tomorrow is a tutorialWritten on 01.12.21 by Markus Bläser There is a tutorial on Dec 2. We meet at 12:15 in room 415 in E1.3. |
Lectures this weekWritten on 14.11.21 by Markus Bläser This week, I am travelling. There will be only one prerecorded lecture which will be uploaded soon. There will be *no* live lectures this week. There will be a new assignment sheet coming out this week. The next tutorial is on Dec 2. |
Tutorial on Nov. 11Written on 10.11.21 (last change on 11.11.21) by Markus Bläser Tomorrow will be a tutorial session (starting as usual at 12:15). There is a separate Zoom link for the tutorial. You find it on the materials webpage. |
Complexity of bilinear problems
Many algorithms use matrix multiplication as a subroutine. In the running times of such algorithms, one often finds a quantity w, the so called exponent of matrix multiplication. w is the infimum over all numbers t such that we can multiply n x n matrices in time n^t. We currently know that w < 2.373. While often used (at least in theory), only very few researchers know how these algorithms work.
We give an overview of the developments of fast algorithms for matrix multiplication. Along the way, we look at some other fundamental problems in algebraic complexity like polynomial evaluation.
This is a 6 CP specialized lecture. It will be online.
Time and Date:
- Monday, 10:15 - 12:00 (online)
- Thursday 12:15 - 14:00 (online)
- First lecture: Thursday, October 21
Lectures are live and will be recorded. The recordings will be made available after the lecture. The Zoom links will be posted under "Materials".
Tutorials:
Every second Thursday, there will be a tutorial instead of a lecture.
Assignments:
There will be bi-weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments. You can submit assignments in groups of up to three persons.
Exams:
There will be oral exams at the end of the semester.
Prerequisites:
Profound knowledge of linear algebra is very helpful.