Using Nondeterminism to Amplify Hardness

Alex Healy, Salil Vadhan, and Emanuele Viola


We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (JCSS `04). 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,

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'.

We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for ``black-box'' hardness amplification procedures (such as ours).


 [ back to Salil Vadhan's research]