From DNF compression to sunflower theorems via regularity
From MaRDI portal
Publication:6314899
DOI10.4230/LIPICS.CCC.2019.5arXiv1903.00580MaRDI QIDQ6314899FDOQ6314899
Authors: Shachar Lovett, Noam Solomon, Jiapeng Zhang 
Publication date: 1 March 2019
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.
This page was built for publication: From DNF compression to sunflower theorems via regularity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6314899)
