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.

Saturday, March 9, 2019

The Catalan Grenade is Accepting Papers!

As an inaugural post to this blog, I will announce that I am perpetually accepting papers! Here at the Catalan Grenade, I'll be going through papers on cool results, old and new, in Combinatorics and Algebra.
Currently, I am a recent graduate from UMass Amherst (Fall 2018), and am waiting to hear back from grad schools. This seems like a fun way to pass the time.

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