Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions

We consider the well-studied problem of learning decision lists using few examples when many irrelevant features are present. We show that smooth boosting algorithms such as MadaBoost can efficiently learn decision lists of length k over n boolean variables using poly(k, log n) many examples provided that the marginal distribution over the relevant variables is "not too concentrated" in an L