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.

No comments:

Post a Comment

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