Hardness amplification in nondeterministic logspace
Sushmita Gupta · Summit (Simon Fraser University) · 2007
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 errorcorrecting 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.