***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Pei Wu (IAS)

Thursday 17th November, 3:00 in Fine Hall 224.

Title: 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.


		----------------------------------


Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)