On sunflowers and matrix multiplication

TY - GEN

T1 - On sunflowers and matrix multiplication

AU - Alon, Noga

AU - Shpilka, Amir

AU - Umans, Christopher

PY - 2012

Y1 - 2012

N2 - We present several variants of the sunflower conjecture of Erdos and Rado [ER60] and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Wino grad [CW90] and Cohn et al [CKSU05] 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 Wino grad [CW90]; 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 [CKSU05] (although it does not seem to impact a second conjecture in [CKSU05] or the viability of the general group-theoretic approach). A surprising consequence of our results is that the Coppersmith-Wino grad conjecture actually implies the Cohn et al. conjecture. The multicolored sunflower conjecture in Z-3 n is a strengthening of the well-known (ordinary) sunflower conjecture in Z-3 n, and we show via our connection that a construction from [CKSU05] 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 [Edel04] on the size of the largest 3-sunflower-free set in Z-3 n.

AB - We present several variants of the sunflower conjecture of Erdos and Rado [ER60] and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Wino grad [CW90] and Cohn et al [CKSU05] 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 Wino grad [CW90]; 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 [CKSU05] (although it does not seem to impact a second conjecture in [CKSU05] or the viability of the general group-theoretic approach). A surprising consequence of our results is that the Coppersmith-Wino grad conjecture actually implies the Cohn et al. conjecture. The multicolored sunflower conjecture in Z-3 n is a strengthening of the well-known (ordinary) sunflower conjecture in Z-3 n, and we show via our connection that a construction from [CKSU05] 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 [Edel04] on the size of the largest 3-sunflower-free set in Z-3 n.

KW - Matrix Multiplication

KW - Sunflower Conjecture

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

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

U2 - 10.1109/CCC.2012.26

DO - 10.1109/CCC.2012.26

M3 - Conference contribution

SN - 9780769547084

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 214

EP - 223

BT - Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012

T2 - IEEE Computer Society Technical Committee on Mathematical Foundations of Computing

Y2 - 26 June 2012 through 29 June 2012

ER -