Prof. Chris Umans: Approaches to bounding the exponent of matrix multiplication
731 views · Published 7 May 2014 · 1:01:45 · Indexed 20 October 2026
Channel: Hebrew University of Jerusalem · 2014 · Education
Prof. Chris Umans (California Institute of Technology) Approaches to bounding the exponent of matrix multiplication 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 omega using commutative coherent configurations, and suggests that commutative coherent configurations may be sufficient to prove omega = 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, omega, equals 2. Finally, we will mention connections between several conjectures implying omega=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.
More from this channel
-
1:22:14
פרופ' אברהם הוכברג- הגן H-19, תקווה חדשה לחולי סרטן
-
1:22:54
מר משה נגבי- על היעדר האחריותיות בדמוקרטיה הישראלית
-
1:30:58
פרופ' ששון צחייק- מדע הכימיה
-
1:13:59
פרופ' אבנר דה שליט- על מורשת, מקום ותכנון בר קיימא
-
1:17:03
פרופ' ארי לאור- עדויות לקיומם של חורים שחורים ענקיים
-
1:07:28
פרופ' ניר שביב- על קרינה קוסמית ואקלים כדור-הארץ
-
1:21:11
ד"ר דני צ'רנוב- השפעת שינויי האקלים על שונית האלמוגים
-
1:06:27
ד"ר ארז ריבק - חידוד הדמות בשמים ובעיניים