דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: On Sunflowers and Matrix Multiplication
event speaker icon
אמיר שפילקה (מדעי המחשב)
event date icon
יום רביעי, 24.10.2012, 12:30
event location icon
טאוב 201
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.
[בחזרה לאינדקס האירועים]