Title: Every boolean decision tree has an influential variable
Speaker: Michael Saks, Rutgers University
Date: April 5, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Boolean decision trees are perhaps the simplest model of boolean function computation. This model measures the cost of a computation entirely by the number of input bits that are accessed. There is a natural notion of a randomized decision tree, which makes use of randomness in choosing which input bits to look at.
The influence of a particular input variable on a boolean function is the probability that, for a uniformly random assignment of the variables, flipping the input variable changes the value of the function.
In this talk, I'll do a brief survey of decision tree complexity and present a new inequality which implies that every balanced boolean function computable by a decision tree of depth d must have a variable of influence at least 1/d. Combining this with another inequality, we deduce new lower bounds for randomized decision tree complexity.
This is joint work with Ryan O'Donnell, Rocco Servedio and Oded Schramm.