MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Approaches to bounding the exponent of matrix multiplication

Chris Umans
California Institute of Technology
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Expert Audience
English

Date, Time and Location

Monday, 24 March 2014
11:40
60 Minutes
E2 1 - Bioinformatik
001
Saarbrücken

Abstract

We begin by describing the ideas behind the state-of-the-art bounds on omega, the exponent of matrix multiplication.

We then present the "group-theoretic" approach of Cohn and Umans as an alternative to these methods, and we generalize this approach from group algebras to general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. We prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on ω using commutative coherent configurations, and suggests that commutative coherent configurations may be sufficient to prove ω=2.

Along the way, we introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s-rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the "s-rank exponent of matrix multiplication" equals 2, then the (ordinary) exponent of matrix multiplication, ω, equals 2.

Finally, we will mention connections between several conjectures implying ω=2, and variants of the classical sunflower conjecture of Erdos and Rado.

No special background is assumed.

Based on joint works with Noga Alon, Henry Cohn, Bobby Kleinberg, Amir Shpilka, and Balazs Szegedy.

Contact

Markus Bläser
--email hidden
passcode not visible
logged in users only

Christine Kiesel, 03/19/2014 16:45
Christine Kiesel, 03/19/2014 16:36 -- Created document.