2026-07-23T07:57:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9455 2024-03-06T10:44:26Z ddc:004 open_access

Sunflowers and Quasi-Sunflowers from Randomness Extractors Li, Xin Lovett, Shachar Zhang, Jiapeng Sunflower conjecture Quasi-sunflowers Randomness Extractors The Erdös-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 (or existing) certain randomness extractors. This allows us to re-derive the known results in a systematic manner, and to reduce the relevant conjectures to the problem of obtaining improved constructions of the randomness extractors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xin Li and Shachar Lovett and Jiapeng Zhang 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.51 urn:nbn:de:0030-drops-94555 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.51 eng https://creativecommons.org/licenses/by/3.0/legalcode