Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-082 | 21st April 2018 17:56

Sunflowers and Quasi-sunflowers from Randomness Extractors

RSS-Feed




TR18-082
Authors: Xin Li, Shachar Lovett, Jiapeng Zhang
Publication: 25th April 2018 04:20
Downloads: 2158
Keywords: 


Abstract:

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