Department of

# Mathematics

Seminar Calendar
for events the day of Tuesday, October 1, 2019.

.
events for the
events containing

More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
    September 2019          October 2019          November 2019
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2  3  4  5  6  7          1  2  3  4  5                   1  2
8  9 10 11 12 13 14    6  7  8  9 10 11 12    3  4  5  6  7  8  9
15 16 17 18 19 20 21   13 14 15 16 17 18 19   10 11 12 13 14 15 16
22 23 24 25 26 27 28   20 21 22 23 24 25 26   17 18 19 20 21 22 23
29 30                  27 28 29 30 31         24 25 26 27 28 29 30



Tuesday, October 1, 2019

1:00 pm in 345 Altgeld Hall,Tuesday, October 1, 2019

#### To Be Announced

###### William Chan (University of North Texas)

3:00 pm in 243 Altgeld Hall,Tuesday, October 1, 2019

#### To Be Announced

###### Michael Brown (UW-Madison)

Abstract: TBA

4:00 pm in 245Altgeld Hall,Tuesday, October 1, 2019

#### Limitations on All Known (and Some Unknown) Approaches to Matrix Multiplication

###### Virginia Vassilevska-Williams   [email] (Massachusetts Institute of Technology)

Abstract: In this talk we will consider the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define generalizations that subsume these two approaches: the Galactic and the Universal method; the latter is the most general method there is. We then design a suite of techniques for proving lower bounds on the value of $\omega$, the exponent of matrix multiplication, which can be achieved by algorithms using many tensors $T$ and the Galactic method. Some of our techniques exploit local' properties of $T$, like finding a sub-tensor of $T$ which is so weak' that $T$ itself couldn't be used to achieve a good bound on $\omega$, while others exploit `global' properties, like $T$ being a monomial degeneration of the structural tensor of a group algebra. The main result is that there is a universal constant $\ell>2$ such that a large class of tensors generalizing the Coppersmith-Winograd tensor $CW_q$ cannot be used within the Galactic method to show a bound on $\omega$ better than $\ell$, for any $q$. We give evidence that previous lower-bounding techniques were not strong enough to show this. The talk is based on joint work with Josh Alman, which appeared in FOCS 2018. More recently, Alman showed how to extend our techniques so that they apply to the Universal method as well. In particular, Alman shows that the Coppersmith-Winograd tensor cannot yield a better bound on $\omega$ than 2.16805 even using the Universal method.