file.pdf (341.65 kB)
Download file

Hardness amplification within NP

Download (341.65 kB)
journal contribution
posted on 01.01.1983, 00:00 authored by Ryan O'Donnell
In 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

History

Publisher Statement

All Rights Reserved

Date

01/01/1983