Events Summer 2020

Advances in Boolean Function Analysis — Improved Bounds for the Sunflower Lemma

Aug. 3, 2020 10:00 am12:00 pm

Add to Calendar

Speaker: 

Shachar Lovett (UC San Diego)

Location: 

Full participation (including the capacity to ask questions) will be available via Zoom webinar

This talk is part of the Advances in Boolean Function Analysis Lecture Series. The series will feature weekly two-hour lectures that aim to address both the broad context of the result and the technical details. Though closely related in theme, each lecture will be self-contained. Join us weekly at 10:00 a.m. PDT, from July 15, 2020 to August 18, 2020. There is a five minute break at the end of the first hour.

Abstract:
A sunflower is a collection of sets whose pairwise intersections are all the same. Erdos and Rado proved the sunflower lemma: any large enough family of sets must contain a sunflower. In the same paper, they conjectured an improved bound, which became known as the "sunflower conjecture". In this talk, I will describe recent progress towards proving the conjecture. The proof builds upon a structure vs pseudo-randomness paradigm and a surprising connection to how DNFs (Disjunctive Normal Forms) simplify under random restrictions.

Joint work with Ryan Alweiss, Kewen Wu and Jiapeng Zhang.