From DNF compression to sunflower theorems via regularity
classification
🧮 math.CO
cs.DM
keywords
sunflowercompressionconjectureapproachboundscomplexitycomputationalimproved
read the original 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 paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.