TY - JOUR

T1 - On sunflowers and matrix multiplication

AU - Alon, Noga

AU - Shpilka, Amir

AU - Umans, Christopher

N1 - Funding Information:
The authors are supported by the following grants: Research of N.A supported in part by an ERC Advanced grant and by NSF Grant No. DMS-0835373. Research of A.S has received funding from the European Community’s Seventh Framework Programme (FP7/2007-2013) under grant agreement number 257575. Research of C.U. is supported by NSF CCF-0846991, CCF-1116111 and BSF grant 2010120.

PY - 2013/6

Y1 - 2013/6

N2 - We present several variants of the sunflower conjecture of Erdo{double acute}s & Rado (J Lond Math Soc 35:85-90, 1960) and discuss the relations among them.We then show that two of these conjectures (if true) imply negative answers to the questions of Coppersmith & Winograd (J Symb Comput 9:251-280, 1990) and Cohn et al. (2005) regarding possible approaches for obtaining fast matrix-multiplication algorithms. Specifically, we show that the Erdo{double acute}s-Rado sunflower conjecture (if true) implies a negative answer to the "no three disjoint equivoluminous subsets" question of Coppersmith & Winograd (J Symb Comput 9:251-280, 1990); we also formulate a "multicolored" sunflower conjecture in ℤ3n and show that (if true) it implies a negative answer to the "strong USP" conjecture of Cohn et al. (2005) (although it does not seem to impact a second conjecture in Cohn et al. (2005) 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 ℤ3n is a strengthening of the well-known (ordinary) sunflower conjecture in ℤ3n, and we show via our connection that a construction from Cohn et al. (2005) 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 Edel (2004) on the size of the largest 3-sunflower-free set in ℤ3n.

AB - We present several variants of the sunflower conjecture of Erdo{double acute}s & Rado (J Lond Math Soc 35:85-90, 1960) and discuss the relations among them.We then show that two of these conjectures (if true) imply negative answers to the questions of Coppersmith & Winograd (J Symb Comput 9:251-280, 1990) and Cohn et al. (2005) regarding possible approaches for obtaining fast matrix-multiplication algorithms. Specifically, we show that the Erdo{double acute}s-Rado sunflower conjecture (if true) implies a negative answer to the "no three disjoint equivoluminous subsets" question of Coppersmith & Winograd (J Symb Comput 9:251-280, 1990); we also formulate a "multicolored" sunflower conjecture in ℤ3n and show that (if true) it implies a negative answer to the "strong USP" conjecture of Cohn et al. (2005) (although it does not seem to impact a second conjecture in Cohn et al. (2005) 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 ℤ3n is a strengthening of the well-known (ordinary) sunflower conjecture in ℤ3n, and we show via our connection that a construction from Cohn et al. (2005) 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 Edel (2004) on the size of the largest 3-sunflower-free set in ℤ3n.

KW - matrix multiplication

KW - sunflowers

UR - http://www.scopus.com/inward/record.url?scp=84877925335&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877925335&partnerID=8YFLogxK

U2 - 10.1007/s00037-013-0060-1

DO - 10.1007/s00037-013-0060-1

M3 - Article

AN - SCOPUS:84877925335

VL - 22

SP - 219

EP - 243

JO - Computational Complexity

JF - Computational Complexity

SN - 1016-3328

IS - 2

ER -