We consider the complexity of properly learning concept classes, i.e. when the learner must output a hypothesis of the same form as the unknown concept. We present the following new upper and lower bounds on well-known concept classes: \vskip .1in $\bullet$ \hangindent=29pt We show that unless $NP = RP$, there is no polynomial-time learning algorithm for DNF formulae where the hypothesis is an OR-of-thresholds. Note that as special cases, we show that neither DNF nor OR-of-thresholds are properly learnable unless $NP = RP$. $\bullet$ \hangindent=29pt Assuming that $NP \not \subseteq DTIME(2^{n^\epsilon})$ for a certain constant $\epsilon <1$ we show that it is not possible to learn size $s$ decision trees by size $s^{k}$ decision trees for any $k \geq 0$. Previous hardness results for learning decision trees held for $k \leq 2$. $\bullet$ \hangindent=29pt We present the first non-trivial upper bounds on properly learning DNF formulae and decision trees. In particular we show how to learn size $s$ DNF by DNF in time $2^{\tilde{O}(\sqrt{n \log s})}$, and how to learn size $s$ decision trees by decision trees in time $n^{O(\log s)}$.