Hints posted and next week: VC dimension

[Adam Kalai]

Hi Class,

I've posted a hint for problem set 1 on the course webpage. If you
use the hint, please mention that fact in your problem set, though it
won't affect your grade. Homework should be turned in to the (*new*)
course mail box which is on the 2nd floor of Ziskind. It's on the
lower-right corner of mailboxes and says "MACHINE LEARNING."

I also wanted to mention that Boaz Nadler today asked about "lower
bounds for learning problems." A better answer to his question is
"Barur -- VC dimension," which gives somewhat tight bounds on the
maximum number of examples you need to provably learn a class. It's
kind of amazing that you can characterize this number, and we'll cover
it next week.

- Adam