An optimal "it ain't over till it's over" theorem
An optimal "it ain't over till it's over" theorem
-
Pei Wu, IAS
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 Ω(1) and all its individual influences are bounded by τ. We show that when restricting all but a ˜Ω((log1/τ)−1) fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function ANDn/Clogn∘ORClogn.
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.