Survey Article on Decision Tree Proofs

Question

I'm looking for a survey article on proofs using decision trees. Presumably it would include at least a passing reference to the proof that the lower bound on comparison-based sorting is $O({n\:log(n)})$. The ideal article would include an overview of the proofs where decision trees have been used, tips and techniques, as well as pitfalls.

---

EDIT:

Wow! Thanks for the quick, helpful replies. My particular interest is in how the technique has been applied to problems in Computational Complexity, and how much traction can be gained from the technique. The Buhrman and Wolf paper looks great; are there any others like it? Thanks!

Answer 1

A somewhat old (2002) survey by Buhrman and Wolf is here. I found it on Wikipedia as well as Googling "decision trees survey". The survey is quite technical.

If you're only interested in sorting-like proofs, then I'm not sure that decision trees are the way to go. There are some other lower bounds on comparison-based tasks that use the adversary method, see for example these brief lecture notes.

There is also the spectacular $n\log n$ lower bound in the algebraic model, see for example these excellent lecture notes. A result from algebraic topology, Milnor's theorem (also associated with several other mathematicians) needs to be used, see this paper for example.

Answer 2

It's not clear from your question what exactly you are interested in or looking for, but some preliminary searching came up with the following:

An overview of the topic can be found at Wikipedia:

• Decision Tree Learning (machine learning)

and also

• Decision Tree (as in decision analysis)

For survey-type articles, see:

• Simplifying Decision Trees: A Survey (pdf)

and

• Complexity measures and Decision Tree Complexities: A Survey (pdf)

If anything looks promising (e.g. skim the references listed on Wikipedia and the articles), that will get you started. Of course, feel free to qualify your question with additional criteria, if I've "missed the mark."

Update:

• See also: Various topologies on trees (survey with "modest proofs")

I also came across some CS "project ideas" webpage for a class which seems to be relevant to your interest. Some of the suggestions, just in the way of a preview, include:

• Inductive inference: This is a whole other way to look at learning from a theoretical CS perspective (more of a recursion theory flavor). Much work in inductive inference predates the work we've discussed in CS 4252. The survey by Angluin and Smith is a good place to get started here.
  

  *The paper of Kushilevitz and Mansour (SIAM J on Computing, 1993) on learning decision trees using the Fourier spectrum; Mansour's survey article on "Learning Boolean functions using the Fourier transform";
  

• Kernel functions and large margin classifiers are an important topic in contemporary machine learning and learning theory research. Read some of the book by Cristianini and Shawe-Taylor ("An introduction to support vector machines").

There are more suggestions, and references on the webpage (link above).

Update 2:

This articles might be of interest to you: see 2010 Decision tree complexity article. It includes reference to the article you were particularly interested in, and many more references that seem to hit on your particular interest.