Boolean decision trees: problems and results, old and new
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.