Confronting Matrix Multiplication
Many algorithms on graphs use fast algorithms for matrix multiplication to derive best known current time bounds. The main subject of this talk comes out of some of our own algorithmic work of this type, which will be reviewed briefly.
Of course, these fast matrix multiplication algorithms are famously difficult to understand, and the constants in front of the O bounds are said to be enormous. Thus, when introducing matrix multiplication to get a best known time bound, there is always a feeling that you might be going down the wrong path entirely; we perhaps should look for algorithms which avoid matrix multiplication entirely.
On the other hand, if a problem could be shown to be as difficult as matrix multiplication, then attempts to solve the problem without resorting to fast matrix multiplication algorithms will be very difficult to find; using matrix multiplication for such problems is certainly justified.
This talk discusses a number of fundamental problems, promoting the idea that if your problem can be shown to be as hard as one of these problems, finding a solution without using matrix multiplication qould require a major breakthrough. We also deal with the issue of why we believe that a single basic problem is insufficient. As a general approach, we would like to advocate that if you solve a problem using fast matrix multiplication, you should attempt to show that it is as hard as one of a small number of fundamental problems.
Joint work with Dieter Kratsch