Roei Tell: Derandomization - Part 2

Roei Tell, University of Toronto, presents a three-part tutorial on derandomization at the Frontiers in Complexity Theory workshop for graduate students held at DIMACS July 29 - August 1, 2024. This is Part 2. Description: The focus of this tutorial is derandomization, and in particular new developments in hardness vs randomness. We will first introduce textbook results, such as the reconstructive paradigm (Nisan-Wigderson, Impagliazzo-Wigderson) and hardness amplification. Then we will study new tools in this area from recent years, focused on constructions of targeted pseudorandom generators from functions hard for uniform algorithms. We'll conclude with very recent applications -- in particular, we will see the construction of a pseudodeterministic polynomial-time algorithm that finds prime numbers! Link to workshop webpage: http://dimacs.rutgers.edu/events/details?eID=2785