### Abstract

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 ℤ_{3}^{n} 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 ℤ_{3}^{n} is a strengthening of the well-known (ordinary) sunflower conjecture in ℤ_{3}^{n}, 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 ℤ_{3}^{n}.

Original language | English (US) |
---|---|

Pages (from-to) | 219-243 |

Number of pages | 25 |

Journal | Computational Complexity |

Volume | 22 |

Issue number | 2 |

DOIs | |

State | Published - Jun 2013 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Mathematics(all)
- Computational Theory and Mathematics
- Computational Mathematics

### Keywords

- matrix multiplication
- sunflowers

## Fingerprint Dive into the research topics of 'On sunflowers and matrix multiplication'. Together they form a unique fingerprint.

## Cite this

*Computational Complexity*,

*22*(2), 219-243. https://doi.org/10.1007/s00037-013-0060-1