Sunflowers - a bridge between complexity, combinatorics and pseudorandomness
Speaker
Jiapeng Zhang, UC San Diego
Time
2019-03-28 14:30:00 ~ 2019-03-28 16:00:00
Location
Room 3-318, SEIEE Building
Host
Chihao Zhang, Assistant Professor, John Hopcroft Center for Computer Science
Abstract
The Erdos-Rado sunflower conjecture is one of the tantalizing open problems in combinatorics. It has profound a lot of connections with theoretical computer science. In this talk, I will focus on the connection between the sunflower conjecture and DNF sparsification. Specifically, I will cover the following two parts:
1.) An improved lower approximation of DNF sparsification lemma.
2.) A connection between upper approximation of DNF sparsification and sunflower structures.
These two results provide some clue to improve the upper bound of sunflower structures. The talk is based on joint works with Xin Li, Shachar Lovett and Noam Solomon.