Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.51
URN: urn:nbn:de:0030-drops-94555
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9455/
Li, Xin ; Lovett, Shachar ; Zhang, Jiapeng
Sunflowers and Quasi-Sunflowers from Randomness Extractors
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{li_et_al:LIPIcs:2018:9455,
author = {Xin Li and Shachar Lovett and Jiapeng Zhang},
title = {{Sunflowers and Quasi-Sunflowers from Randomness Extractors}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {51:1--51:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-085-9},
ISSN = {1868-8969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9455},
URN = {urn:nbn:de:0030-drops-94555},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.51},
annote = {Keywords: Sunflower conjecture, Quasi-sunflowers, Randomness Extractors}
}
| Keywords: | Sunflower conjecture, Quasi-sunflowers, Randomness Extractors | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 13.08.2018 |
