Randomness vs structure — DNF compression and sunflower lemma (Kewen Wu)

Abstract

DNFs (Disjunctive Normal Forms) are widely studied in theoretical computer science, with applications in logic, complexity theory, learning theory, cryptography and more. Similarly, set systems (also known as hypergraphs) are widely studied in combinatorics, with numerous applications both in combinatorics and in mathematics at large. In particular, there is a correspondence between DNFs and set systems.

We make progress on two important problems in these areas with the same underlying framework: randomness vs structure.

• DNF compression

A DNF is a disjunction of terms, and a term is a conjunction of literals. The size of a DNF is the number of terms, and its width is the maximal number of variables in a term. We prove that DNFs of small width can always be approximated by DNFs of small size and same width, where we obtain sharp bounds. This in particular resolves and further strengthens a conjecture of Gopalan, Meka and Reingold (Computational Complexity, 2013). In fact, this result applies to decision lists, a computational model that generalizes DNFs.

• Sunflower lemma

A sunflower with r petals is a collection of r sets with the same pairwise intersection. Erd?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 contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to c^w for some constant c. We improve the bound to about (log w)^w. In fact, we prove the result for a robust notion of sunflowers, for which the bound we obtain is tight up to lower order terms.

Time

Speaker

Room