Members’ Seminar

In this talk I will discuss the Sunflower Lemma and similar lemmas that prove (in various contexts) that a set/distribution can be partitioned into a structured part and a "random-looking" part. I will introduce communication complexity as a key model for understanding computation and more generally for reasoning about information bottlenecks. I will describe our recent Lifting theorems which prove in a very general way how efficient communication protocols can be well-approximated by "simple" protocols. Like Razborov's theorem, the main component in the proof is a theorem quite similar to the Sunflower Lemma. We will show how to use Lifting to reprove Razborov's theorem as well as other state-of-the-art circuit lower bounds. Time permitting, we will present other applications of Lifting (such as lower bounds for refuting random CNF formulas and the resolution of the Alon-Saks-Seymour conjecture) and challenges to proving nonmonotone circuit lower bounds.