文章基本信息

标题：From DNF compression to sunflower theorems via regularity
本地全文：下载
作者：Shachar Lovett ; Noam Solomon ; Jiapeng Zhang 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2019
卷号：2019
页码：1-14
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：
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 [Computational Complexity 2013]. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.