Influences and Decision Tree Complexity

COMPUTER SCIENCE/DISCRETE MATH, I
Topic:Influences and Decision Tree Complexity
Speaker:Michael Saks
Affiliation:Rutgers University
Date:Monday, November 1
Time/Room:11:15am - 12:15pm/S-101

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.