Abstract
The first session of this talk will take place on Tuesday, September 1 from 11:00 am – 12:00 pm; the second session of this talk will take place on Wednesday, September 2 from 11:00 am – 12:00 pm; the fourth session of this talk will take place on Friday, September 4 from 1:30 pm – 2:30 pm.
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.