pdf icon
Volume 18 (2022) Article 2 pp. 1-18
RANDOM 2018 Special Issue
Sunflowers and Robust Sunflowers from Randomness Extractors
Received: September 19, 2018
Revised: May 15, 2021
Published: January 31, 2022
Download article from ToC site:
[PDF (369K)] [PS (1460K)] [Source ZIP]
Keywords: CNF-DNF Formulas, Extractors, Combinatorics, Sunflowers
ACM Classification: F.1.3, G.2.1
AMS Classification: 05D10, 68Q17, 68Q25

Abstract: [Plain Text Version]

The Erdős--Rado Sunflower Theorem (J. London Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding Sunflower Conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to robust sunflowers, where similar conjectures emerge about the optimal parameters for which it is expected to hold.

We exhibit a surprising connection between the existence of sunflowers and robust sunflowers in sufficiently large families of sets and the problem of constructing certain randomness extractors. This allows us to rederive the known results in a systematic manner. Our techniques have also motivated significant subsequent progress on the Sunflower Conjecture by Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang (STOC'20 and Annals of Math. 2021).


A preliminary version of this paper appeared in the Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM'18).