Computer Science Colloquium - Chris Umans '96

Friday, April 27 @ 2:35pm, Wege Auditorium

“New Algorithms for Matrix Multiplication ”

It is widely believed that there is an algorithm for multiplying n-by-n matrices that runs in time roughly n^2. However, the best algorithms we know for this problem run in time n^{2.373}, and there is reason to believe that the prevailing approach cannot do much better.

In this talk I’ll describe a new approach to producing fast algorithms for matrix multiplication. In this framework, one devises algorithms by constructing non-abelian groups with certain appealing properties. The resulting algorithms are natural and are based on taking the Discrete Fourier Transform over these groups.

I’ll describe recent developments that connect to the recent resolution of the “cap-set conjecture” in combinatorics, and an easy-to-state conjecture that would imply an optimal matrix multiplication algorithm.

The talk will be self-contained and does not assume any specialized math background.

Dr. Umans received his undergraduate degree in Computer Science and Mathematics from Williams College and his Ph.D. in Computer Science from Berkeley in 2000. After spending two years as a postdoc in the Theory Group at Microsoft Research, he joined the Computer Science faculty at Caltech in 2002, where he is currently Professor of Computer Science. His research interests are in theoretical computer science, especially computational complexity, randomness in computation, and algebraic complexity and algorithms. He serves as an editor of the Journal of Computer and System Sciences, Algorithmica, Computational Complexity, ACM Transactions on Computation Theory, and Theory of Computing. He is a member of the scientific board of the Electronic Colloquium on Computational Complexity and the moderator for the Computational Complexity section of the arXiv. Dr. Umans is the recipient of an NSF CAREER award, an Alfred P. Sloan Research Fellowship, and a Simons Foundation Investigator award, as well as several best-paper and teaching awards.