License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2019.5
URN: urn:nbn:de:0030-drops-108277
Go to the corresponding LIPIcs Volume Portal

Lovett, Shachar ; Solomon, Noam ; Zhang, Jiapeng

From DNF Compression to Sunflower Theorems via Regularity

LIPIcs-CCC-2019-5.pdf (0.4 MB)


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 the DNF compression result. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.

BibTeX - Entry

  author =	{Shachar Lovett and Noam Solomon and Jiapeng Zhang},
  title =	{{From DNF Compression to Sunflower Theorems via Regularity}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Amir Shpilka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-108277},
  doi =		{10.4230/LIPIcs.CCC.2019.5},
  annote =	{Keywords: DNF sparsification, sunflower conjecture, regular set systems}

Keywords: DNF sparsification, sunflower conjecture, regular set systems
Collection: 34th Computational Complexity Conference (CCC 2019)
Issue Date: 2019
Date of publication: 16.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI