A hard problem is one which cannot be easily computed by efficient algorithms. Hardness amplification is a procedure which takes as input a problem of mild hardness and returns a problem of higher hardness. This is closely related to the task of decoding certain error-correcting codes. We show amplification from mild average case hardness to higher average case hardness for nondeterministic logspace and worst-to-average amplification for nondeterministic linspace. Finally we explore possible ways of improving the parameters of our hardness amplification results.
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact firstname.lastname@example.org.
Member of collection