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

The Catalan Grenade is Accepting Papers!

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

Number-on-the-Forehead Communication Complexity