Complexity of bilinear problems Markus Bläser, Julian Dörfler

News

08.12.2021

No lecture on Dec 9.

There will be no lecture tomorrow. There will be an extra tutorial next week tba.

01.12.2021

Tomorrow is a tutorial

There is a tutorial on Dec 2. We meet at 12:15 in room 415 in E1.3.

14.11.2021

Lectures this week

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.

10.11.2021

Tutorial on Nov. 11

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.

 



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