An Optimal “It Ain’t Over Till It’s Over” Theorem
Ronen Eldan, Avi Wigderson, Pei Wu · 2023
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 Ω(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 =n/Clogn∘Clogn.