{
  "id": "1903.00580",
  "version": "v1",
  "published": "2019-03-01T23:50:23.000Z",
  "updated": "2019-03-01T23:50:23.000Z",
  "title": "From DNF compression to sunflower theorems via regularity",
  "authors": [
    "Shachar Lovett",
    "Noam Solomon",
    "Jiapeng Zhang"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-03-01T23:50:23.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "dnf compression",
      "sunflower theorems",
      "sunflower conjecture",
      "regularity",
      "computational complexity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}