Computer Science and Engineering

Faculty Candidate Seminar

On Sunflowers and Its Friends in Computer Science and Mathematics

Jiapeng ZhangPostdocHarvard University
WHERE:
3725 Beyster BuildingMap
SHARE:
Abstract:
 
The Erdős-Rado sunflower is a useful structure in both computer science and mathematics. Even though it is a simple notation, it has deep connections to other areas, such as data structures, cryptography, computational complexity, combinatorics, and Ramsey theory. The sunflower conjecture is one of the tantalizing open problems in combinatorics. In my talk, I will cover three parts related to the sunflower problem. 


1). I will quickly review some old friends of sunflowers, including matrix multiplication and computational complexity. Then I will introduce a new friend of sunflowers, Boolean function analysis.
 
2). Secondly, I will show how to exponentially improve the Erdős-Rado’s sunflower lemma via a random restriction idea, which was first introduced to prove circuit lower bounds.
 

3). Lastly, I will also briefly mention some applications (or potential applications) of our new sunflower bounds, including applications in communication complexity, combinatorial optimization, and random graph theory. 

Jiapeng Zhang is a postdoc at Harvard with Prof. Salil Vadhan. He did his PhD at UC San Diego with Prof. Shachar Lovett. His research focuses on boolean function analysis, computational complexity, learning theory and cryptography.

Organizer

Cindy Estell

Faculty Host

Mahdi Cheraghchi