An optimal "it ain't over till it's over" theorem
An optimal "it ain't over till it's over" theorem
In the talk, we discuss 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 $\Omega(1)$ and all its individual influences are bounded by $\tau$. We show that when restricting all but a $\tilde{\Omega}((\log1/\tau)^{-1})$ fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function $AND_{n/C\log n} \circ OR_{C\log n}$.
We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability 1-o(1). This gives a sharp version of the ``it ain't over till it's over'' theorem due to Mossel, O'Donnell, and Oleszkiewicz.