Fall 2018

Derandomization from Circuit Lower Bounds II

Tuesday, August 21st, 2018 3:30 pm4:30 pm

Add to Calendar

We will review how circuit lower bounds have been used to design algorithms, and in particular, to give deterministic analogs of randomized algorithms. In the first hour, we will discuss the generic “hardness as randomness” paradigm, following Nisan and Wigderson. We will also discuss using this paradigm in the algebraic circuit setting. In the second hour, we will show how specific lower bound techniques (algebraic approximation and random restrictions) have been used to construct efficient pseudo-random generators.