Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-082 | 21st April 2018 17:56

Sunflowers and Quasi-sunflowers from Randomness Extractors


Authors: Xin Li, Shachar Lovett, Jiapeng Zhang
Publication: 25th April 2018 04:20
Downloads: 1947


The Erdos-Rado sunflower theorem (Journal of Lond. 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 quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which it holds.

In this work, we exhibit a surprising connection between the existence of sunflowers and quasi-sunflowers in large enough set systems, and the problem of constructing certain randomness extractors. This allows us to re-derive the known results in a systemic manner, and to reduce the relevant conjectures to the problem of obtaining improved constructions of the randomness extractors.

ISSN 1433-8092 | Imprint