pith. sign in

arxiv: 1903.00580 · v2 · pith:OTE3DD5Knew · submitted 2019-03-01 · 🧮 math.CO · cs.DM

From DNF compression to sunflower theorems via regularity

classification 🧮 math.CO cs.DM
keywords sunflowercompressionconjectureapproachboundscomplexitycomputationalimproved
0
0 comments X
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.