file.pdf (341.65 kB)
Hardness amplification within NP
journal contribution
posted on 1983-01-01, 00:00 authored by Ryan O'DonnellIn this paper we investigate the following question: if NP is slightly hard on average, is it very hard on average?
The computational result we prove essentially matches an information-theoretic bound