##### Department of Mathematics,

University of California San Diego

****************************

### Special Recruitment Colloquium

## Dr. Misha Alekhnovitch

#### IAS Princeton

## Learnability and Automatizability

##### Abstract:

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)}$.

Host: Sam Buss

### January 24, 2005

### 3:00 PM

### AP&M 7321

****************************