Wednesday, June 3, 2020

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.

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 a...