Distribution-Specific Agnostic Boosting
  We consider the problem of boosting the accuracy of weak learning algorithms
in the agnostic learning framework of Haussler (1992) and Kearns et al. (1992).
Known algorithms for this problem (Ben-David et al., 2001; Gavinsky, 2002;
Kalai et al., 2008) follow the same strategy as boosting algorithms in the PAC
model: the weak learner is executed on the same target function but over
different distributions on the domain. We demonstrate boosting algorithms for
the agnostic learning framework that only modify the distribution on the labels
of the points (or, equivalently, modify the target function). This allows
boosting a distribution-specific weak agnostic learner to a strong agnostic
learner with respect to the same distribution.
  When applied to the weak agnostic parity learning algorithm of Goldreich and
Levin (1989) our algorithm yields a simple PAC learning algorithm for DNF and
an agnostic learning algorithm for decision trees over the uniform distribution
using membership queries. These results substantially simplify Jackson's famous
DNF learning algorithm (1994) and the recent result of Gopalan et al. (2008).
  We also strengthen the connection to hard-core set constructions discovered
by Klivans and Servedio (1999) by demonstrating that hard-core set
constructions that achieve the optimal hard-core set size (given by Holenstein
(2005) and Barak et al. (2009)) imply distribution-specific agnostic boosting
algorithms. Conversely, our boosting algorithm gives a simple hard-core set
construction with an (almost) optimal hard-core set size.
