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.