*Boolean decision trees: problems and
results, old and new*

Michael Saks

Abstract:

Boolean decision trees are perhaps
the simplest algorithmic model

for computing Boolean functions. In
this model, the cost of a computation

is simply 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. As
with any model of computation, a

primary goal of the research is to obtain
upper and lower bounds for specific

functions and general classes of functions. The
methods are quite varied,

including adversary arguments,
algebraic/combinatorial topology,

information theory, and Fourier
analysis.

In this talk, I'll
give an overview of some recent and not-so-recent results,

and some open problems.