Computer Science/Discrete Mathematics Seminar I

In this talk, I'll present a new inequality which, for an arbitrary boolean function, relates the influence of its variables to decision tree computation of the function. Combining this with another inequality due to Schramm and Steif, we deduce new general lower bounds for randomized decision tree complexity. This is joint work with Ryan O'Donnell, Rocco Servedio and Oded Schramm.