Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2019.5
URN: urn:nbn:de:0030-drops-108277
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10827/
Lovett, Shachar ; Solomon, Noam ; Zhang, Jiapeng
From DNF Compression to Sunflower Theorems via Regularity
| pdf-format: |
|
Abstract
The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold (Computational Complexity, 2013). In this paper, we show that improved bounds for DNF compression imply improved bounds for the sunflower conjecture, which is the reverse direction of the DNF compression result. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.
BibTeX - Entry
@InProceedings{lovett_et_al:LIPIcs:2019:10827,
author = {Shachar Lovett and Noam Solomon and Jiapeng Zhang},
title = {{From DNF Compression to Sunflower Theorems via Regularity}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {5:1--5:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-116-0},
ISSN = {1868-8969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10827},
URN = {urn:nbn:de:0030-drops-108277},
doi = {10.4230/LIPIcs.CCC.2019.5},
annote = {Keywords: DNF sparsification, sunflower conjecture, regular set systems}
}
| Keywords: | DNF sparsification, sunflower conjecture, regular set systems | |
| Seminar: | 34th Computational Complexity Conference (CCC 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 16.07.2019 |
