The Power of Distinguishing Simple from Random

Valentine Kabanets (Simon Fraser University) gave a two-part tutorial presentation on the Power of Distinguishing Simple from Random, at the Simons Institute's Meta-Complexity Boot Camp on January 17. Here we present Part 1 of the tutorial, in which he discusses the connections between pseudorandomness and learning.