ECCC-Report TR11-067https://eccc.weizmann.ac.il/report/2011/067Comments and Revisions published for TR11-067en-usSun, 31 Jul 2011 11:26:44 +0300
Comment 1
| possible typo |
Dennis Farr
https://eccc.weizmann.ac.il/report/2011/067#comment1I think the definition of a k-sunflower in Def 2.1 has a bound variable i on the right hand side which actually needs to be free, which can be done by renaming it something other than i, j, or k, say p.Sun, 31 Jul 2011 11:26:44 +0300https://eccc.weizmann.ac.il/report/2011/067#comment1
Paper TR11-067
| On Sunflowers and Matrix Multiplication |
Noga Alon,
Amir Shpilka,
Chris Umans
https://eccc.weizmann.ac.il/report/2011/067We present several variants of the sunflower conjecture of Erd\H{o}s 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 Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. Specifically, we show that the Erd\H{o}s-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 $\mathbb{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 a second conjecture in that paper or the viability of the general group theoretic approach). A surprising consequence of our results is that the Coppersmith-Winograd conjecture actually implies the Cohn et al. conjecture.
The multicolored sunflower conjecture in $\mathbb{Z}_3^n$ is a strengthening of the well-known (ordinary) sunflower conjecture in $\mathbb{Z}_3^n$, and we show via our connection that a construction of Cohn et al. yields a lower bound of $(2.51\ldots)^n$ on the size of the largest {\em multicolored} 3-sunflower-free set, which beats the current best known lower bound of $(2.21\ldots)^n$ on the size of the largest 3-sunflower-free set in $\mathbb{Z}_3^n$.Mon, 25 Apr 2011 23:15:39 +0300https://eccc.weizmann.ac.il/report/2011/067