Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Approximate sunflowers:
TR19-028 | 1st March 2019
Shachar Lovett, Noam Solomon, Jiapeng Zhang

From DNF compression to sunflower theorems via regularity

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint