Mathematical Conversations

What is common to the Szemeredi Regularity lemma in graph theory, the Green-Tao result on arithmetic progressions in the primes, the Schapire Boosting algorithm in machine learning and Impagliazzo Hard-Core set theorem in computational complexity? Well, all are important and celebrated results in their own domains of course, but their commonality goes much deeper than that. There is one principle, that quantifies the interplay between structure and (pseudo)-randomness, which plays the same central role in all of them. I will try to explain all this in the ample time I was given. The talk is based mainly on papers of Tao-Ziegler and Reingold-Trevisan-Tulsiani-Vadhan.