What machine learning classifiers are the most parallelizeable? What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try?

Off hand it looks to me like some standard classifiers I know of stack up as follows but I could be totally wrong:

Random Forests - Very parallelizeable as long as each machine can hold all the data (i.e. can't divide up the training data per se, but otherwise parallelizeable).

Boosting - ?

Support Vector Machine - Not very parallelizable.

Decision trees - Can be divided up in part, but not very efficiently.
There have been efforts to parallelize most of the well-known classifiers, including boosting [a paper], SVM [a paper], and even decision trees [a paper].  Of course, by admitting parallelism, you sometimes lose out on other aspects, whether it be algorithm implementability, sample complexity, or other usual suspects.

From the theory end, the question is harder because when you talk about learning you have to think about the target function.  For example, we don't even know decision trees to be PAC-learnable, so if the target (as well as the method) is a decision tree, then we can't even learn it (yet) without introducing extra facets to the problem.  Boosting gets around that by assuming a weak learning condition, SVM a margin, etc. I think those assumptions transfer to the parallel case to give you PAC learning.  

But as always, there's a big gap between the frontiers (and thereby concerns) of theory and of practice.   For example, in practice, it matters whether the parallelism is over cores or clusters.  One algorithm developed especially for practical use in large-data settings is VW, and it's starting to support parallelism.  You might be interested in the papers in the NIPS 2010 workshop on practical parallel learning.