went to Leslie Valiant for inventing the notion of PAC (probably approximately correct) as part of his work
on the theory of the learnable.
(I hope you still remember that the Turing award for this year went to Judea Pearl for his work on
ps: I misspoke a bit when talking about "sample complexity"--it is the least number of examples needed to learn the
concept by any algorithm (not the "most"). You saw that the inequality on the slide was N >=