Boolean decision trees: problems and results, old and new

Michael Saks

Rutgers University



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.