Using Nondeterminism to Amplify Hardness
Salil Vadhan, Harvard University
August 18th, 2004

Abstract

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC `02). We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a function f' such that any circuit of size s'(n) fails to compute f' on a 1/2 - 1/s'(n) fraction of inputs, where s'(n) is polynomially related to s(\sqrt{n}). In particular,

- If s(n) is superpolynomial, we amplify to hardness 1/2-1/superpoly(n).

- If s(n)=2^{n^a} for a constant a>0, we amplify to hardness 1/2-1/2^{n^b} for a constant b>0.

- If s(n)=2^{an} for a constant a>0, we amplify to hardness > 1/2-1/2^{b\sqrt{n}} for a constant b>0.

These improve the results of O'Donnell, which only amplified to 1/2-1/\sqrt{n}. O'Donnell also proved that no construction of a certain general form could amplify beyond 1/2-1/n. We bypass this barrier by using both *derandomization* and *nondeterminism* in the construction of f'.

Joint work with Alex Healy and Emanuele Viola.