TR04-087 Authors: Alexander Healy, Salil Vadhan, Emanuele Viola

Publication: 22nd October 2004 16:56

Downloads: 2856

Keywords:

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