An Optimal "It Ain't Over Till It's Over" Theorem

Ronen Eldan, Avi Wigderson, Pei Wu

We study the probability of Boolean functions with small max influence to become constant under random restrictions. Let $f$ be a Boolean function such that the variance of $f$ is…