ECCC-Report TR04-087https://eccc.weizmann.ac.il/report/2004/087Comments and Revisions published for TR04-087en-usFri, 22 Oct 2004 16:56:41 +0200
Paper TR04-087
| Using Nondeterminism to Amplify Hardness |
Alexander Healy,
Salil Vadhan,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2004/087We 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).
Fri, 22 Oct 2004 16:56:41 +0200https://eccc.weizmann.ac.il/report/2004/087