文章基本信息

标题：From DNF Compression to Sunflower Theorems via Regularity
本地全文：下载
作者：Shachar Lovett ; Noam Solomon ; Jiapeng Zhang 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：137
页码：1-14
DOI：10.4230/LIPIcs.CCC.2019.5
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：DNF sparsification; sunflower conjecture; regular set systems