### DIMACS Theoretical Computer Science Seminar

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.