9:00  9:50 
1. Introduction 
The PAC model. What is known about basic PAC problems 

2. Proving Hardness: Learning vs. Computation 
Inapplicability of NPhardness techniques.
Boosting vs. Hardness of Approximation 

3. Hardness under Cryptographic assumptions 

9:50  10:05 
Break 

10:05  10:45 
4. Hardness under Average Case assumptions 