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:
and also
For survey-type articles, see:
and
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:
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.