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)=s(\sqrt{n})^{\Omega(1)}$ fails to compute $f'$ on a $1/2 - 1/s'(n)$ fraction of inputs. In particular, - If $s(n)=n^{\omega(1)}$, we amplify to hardness $1/2-1/n^{\omega(1)}$. - If $s(n)=2^{n^{\Omega(1)}}$, we amplify to hardness $1/2-1/2^{n^{\Omega(1)}}$. - If $s(n)=2^{\Omega(n)}$, we amplify to hardness $1/2-1/2^{\Omega(\sqrt{n})}$. 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 {\em derandomization} and {\em 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).