Graduate Theoretical Computer Science Seminar
Jeremy Kun
UIC
Hardness amplification using error correcting codes
Abstract: We'll discuss the applications of efficient local decoding techniques to amplify a worst-case hard function for circuits to an average-case hard function. Together with a previous talk by Adam Lelkes on the Nisan-Wigderson pseudoranom generator, this gives a complete derandomization of BPP from the existence of a worst-case hard function.
Monday March 2, 2015 at 4:00 PM in SEO 427