Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-028 | 7th June 2019 00:43

From DNF compression to sunflower theorems via regularity

RSS-Feed




Revision #1
Authors: Shachar Lovett, Noam Solomon, Jiapeng Zhang
Accepted on: 7th June 2019 00:43
Downloads: 53
Keywords: 


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 [Computational Complexity 2013]. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.



Changes to previous version:

Fix some bugs.


Paper:

TR19-028 | 1st March 2019 21:45

From DNF compression to sunflower theorems via regularity





TR19-028
Authors: Shachar Lovett, Noam Solomon, Jiapeng Zhang
Publication: 2nd March 2019 04:49
Downloads: 338
Keywords: 


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 [Computational Complexity 2013]. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.



ISSN 1433-8092 | Imprint