Hardness amplification in nondeterministic logspace

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2007
Authors/Contributors
Abstract
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.
Document
Copyright statement
Copyright is held by the author.
Permissions
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 summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Attachment Size
etd2961.pdf 600.13 KB