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