On Sunflowers and Matrix Multiplication
- Creators
- Alon, Noga
- Shpilka, Amir
- Umans, Christopher
Abstract
We present several variants of the sunflower conjecture of Erdő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ő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 Zn₃ 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 Zn₃ is a strengthening of the well-known (ordinary) sunflower conjecture in Zn₃, and we show via our connection that a construction of Cohn et al. yields a lower bound of (2.51...)^n on the size of the largest multicolored 3-sunflower-free set, which beats the current best known lower bound of (2.21...)^n on the size of the largest 3-sunflower-free set in Zn₃.
Additional Information
© 2011 Computational Complexity Foundation (CCF). Research supported in part by an ERC Advanced Grant. The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement number 257575. Research supported in part by NSF CCF-0830787. We thank Adam Murcus for helpful discussions in an early stage of this research. We thank Henry Cohn, Bobby Kleinberg, and Balázs Szegedy for help in formulating the weak sunflower conjecture in ZnD, and for useful discussions.Attached Files
Published - TR11-067.pdf
Files
Name | Size | Download all |
---|---|---|
md5:84277194ab9bb42cc37ffdaa52a5359f
|
685.3 kB | Preview Download |
Additional details
- Eprint ID
- 100074
- Resolver ID
- CaltechAUTHORS:20191126-142038137
- 257575
- European Research Council (ERC)
- CCF-0830787
- NSF
- Created
-
2019-11-26Created from EPrint's datestamp field
- Updated
-
2021-08-18Created from EPrint's last_modified field