Derandomization of BPP Using Hitting Set Generators

In 1999, Goldreich, Vadhan, and Wigderson wrote a beautiful and simple paper that the derandomization of RP through hitting set generators also derandomizes BPP.

In the following write up, I survey basic results on RP and BPP, as well as the results of this paper. If you are too lazy to read, feel free to watch a recorded lecture I made on the topic while quarantined at my grandfather's house!

If you are wondering why I look like I am in a witness protection program in the recording, it is cause my DIY whiteboard fails with any internal lighting.

Comments

Popular posts from this blog

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

Number-on-the-Forehead Communication Complexity