Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Sunflower conjecture:
TR18-082 | 21st April 2018
Xin Li, Shachar Lovett, Jiapeng Zhang

Sunflowers and Quasi-sunflowers from Randomness Extractors

The Erdos-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which ... more >>>

TR18-190 | 5th November 2018
Shachar Lovett, Jiapeng Zhang

DNF sparsification beyond sunflowers

There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in ... more >>>

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

TR19-110 | 23rd August 2019
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

Improved bounds for the sunflower lemma

A sunflower with $r$ petals is a collection of $r$ sets so that the
intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ... more >>>

ISSN 1433-8092 | Imprint