Derandomization

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

This series of talks was part of the F ine-Grained Complexity and Algorithm Design Boot Camp. Videos for each talk area available through the links above.

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.

Derandomization

This series of talks was part of the Fine-Grained Complexity and Algorithm Design Boot Camp. Videos for each talk area available through the links above.

This series of talks was part of the F ine-Grained Complexity and Algorithm Design Boot Camp. Videos for each talk area available through the links above.