Lecture 1: Boolean Hardness to Derandomization
Lecture 2: Derandomization to Boolean Circuit Lower Bounds
Lecture 3: The Easy Witness Lemma
Lecture 4: Connections Between Hardness and Randomness in the Algebraic Setting
Speaker: Russell Impagliazzo, UC San Diego
Randomness has become an essential tool in algorithm design. However, for many randomized algorithms, later research shows how to modify therandomized algorithm to construct deterministic algorithms solving the same problems. This raises the question: can any randomized algorithm be derandomized, or are randomized algorithms a fundamentally different model of computation from deterministic algorithms? Starting with Blum, Micali, and Yao in the early 1980's, the algorithmic question of producing general deterministic algorithms has been linked to the central complexity question of proving lower bounds, especially for Boolean circuits. Later research extended and deepened this connection. In this series of talks, we will give precise statements for such connections, and at least an intuitive idea of many of the proofs.