An exposition of (theoretical) derandomization of randomized algorithms. Wigderson received the Turing Award last month for work in this area. https://www.youtube.com/watch?v=mZck0N_T9Cs
I think I first learned about the Impagliazzo-Wigderson theorem from Scott Aaronson's lecture notes for his wide-ranging (and fast-moving) course Quantum Computing Since Democritus, which I highly recommend. The relevant lecture is https://www.scottaaronson.com/democritus/lec7.html
Add comment