Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 09, 2015, 12:15 pm
Duration: 45 minutes
Location: OAT S15/S16/S17
Speaker: Alexandra Maximova
Boolean Matrix Multiplication is one of the most fundamental problems in computer science. Two lines of theoretical research have been explored to solve this problem: algebraic algorithms, exploiting a ring structure and clever cancellations, and combinatorial algorithms, exploiting combinatorial redundances arising from representing matrices as graphs, often invoking lookup tables. In this talk I will summarize the findings of the "combinatorial" line of research, with particular focus on the recent algorithm by Timothy Chan .
 Timothy M. Chan. 2015. Speeding up the four Russians algorithm by about one more logarithmic factor. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '15). SIAM 212-217.
Automatic MiSe System Software Version 1.4803M | admin login