### DIMACS Theoretical Computer Science Seminar

Title: On Sunflowers and Matrix Multiplication

Speaker: **Amir Shpilka**, Technion

Date: Wednesday, September 12, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We present several variants of the sunflower conjecture of Erdos and Rado and
discuss the relations among them. We then show that two of these conjectures
(if true) imply negative answers to questions of Coppersmith and Winograd and
of Cohn et al regarding possible approaches for obtaining fast matrix
multiplication algorithms. Specifically, we show that the Erdos-Rado sunflower
conjecture (if true) implies a negative answer to the ``no three disjoint
equivoluminous subsets'' question of Coppersmith and Winograd; we also
formulate a ``multicolored'' sunflower conjecture in $\Z_3^n$ and show that
(if true) it implies a negative answer to the ``strong USP'' conjecture of
Cohn et al (although it does not seem to impact their second conjecture or
the viability of the general group-theoretic approach).

Joint work with Noga Alon and Chris Umans.

See: http://www.cs.rutgers.edu/~allender/theory-fall12.html