Which classifier should I use for sparse boolean features?
Mapping your inputs into a sparse matrix and using logistic regression with an $\ell_1$ penalty should work well. In R this is very straight forward with the glmnet and matrix libraries. 

Additionally, if you have boolean features with a low frequency, you can filter some of them by taking a subset with at least some number of observations.

Here's a quick simulation in R of a lasso logistic regression with sparse features. 

library(glmnet)
library(Matrix)

n &lt;- 1e5
set.seed(420)

# These are all converted to boolean variables since they're arbitrary categories
ls &lt;- data.frame(cat1=sample(letters, n, replace=TRUE), 
                 cat2=sample(letters, n, replace=TRUE), 
                 cat3=sample(letters, n, replace=TRUE))
ls$cat1cat2 &lt;- factor(paste(ls$cat1, ls$cat2, sep="-"))
xs &lt;- sparse.model.matrix(~.-1,data=ls)
betas&lt;- rnorm(dim(xs)[2])
error &lt;- runif(n)

ytrue &lt;- xs %*%betas
ylogit &lt;- 1/(1 + exp(- (ytrue + error))
ylabel &lt;- ifelse(ylogit&gt;0.5,1,0)

trainfilter &lt;- runif(n)&lt;=0.3
sparsemodel &lt;- cv.glmnet(x=xs[trainfilter,],
                         y=ylabel[trainfilter],
                         alpha=1,
                         nfolds=3,
                         family='binomial')

preds &lt;- predict(sparsemodel, xs, s='lambda.min', type='class')
print(table(ylabel, preds))


The classifier doesn't matter as much in this case as the underlying algorithm's ability to handle sparse matrices. 

It's also worth noting that you can handle sparse boolean features by mapping them to arbitrary numeric indices and running them through a tree based algorithm (e.g., Random Forest or Gradient Boosting). In practice, this seems to work well.