# Using Nondeterminism to Amplify Hardness

Alex Healy, Salil Vadhan, and Emanuele Viola

### Abstract

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,

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

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

### Versions

• In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 04), pages 192-201, Chicago, Illinois, June 2004.  ACM.
[official ACM page]
• Preliminary full version, October 2004. [postscript][pdf]
• SIAM Journal on Computing. 35 (4): 903-931, 2006. Special Issue on STOC 2004. [postscript][pdf][official SICOMP page]

[ back to Salil Vadhan's research]