MENU 
Faculty Candidate Seminar
On Sunflowers and Its Friends in Computer Science and Mathematics
Jiapeng ZhangPostdocHarvard University
WHERE:
3725 Beyster BuildingMap
WHEN:
Tuesday, January 14, 2020 @ 10:30 am - 11:30 am
This event is free and open to the publicAdd to Google Calendar
This event is free and open to the publicAdd to Google Calendar
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.