# The sensitivity conjecture

A few weeks ago Hao Huang proved a significant 30-year old open conjecture, giving a elementary proof. The problem was the "sensitivity conjecture", relating "sensitivity", a certain measure of the complexity of a boolean function $f : \{0,1\}^n \to \{0,1\}$, to a host of other measures. Concretely, the sensitivity conjecture had already been reduced to the following: Given a subset $Q \subset \{0,1\}^n$ with at least $2^{n-1} + 1$ elements, there exists a $q \in Q$ with at least $\sqrt{n}$ neighbours. Huang's proof has since been polished a little by others, and there's now a 1-page proof using only 1116 material!

This is a little outside our usual fare, but it seems a timely and fun topic, so it'll be the topic of this afternoon's quantum seminar. The proof is so easy it should only take a few minutes, so I'll also give some background on the conjecture, and the discovery of the proof. We'll meet at 2pm (not the usual 3pm, so algebraic topology students can come), and in 1.33 (the main seminar room) so we have space. All students welcome, so please feel free to tell others.

(I'll have to run after the seminar, but if anyone wants to go for a drink at 5pm I'd be happy to join.)