Hardness amplification is the fundamental task of
converting a $\delta$-hard function $f : {0,1}^n ->
{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,
where $f$ is $\gamma$-hard if small circuits fail to
compute $f$ on at least a $\gamma$ fraction of the
inputs. Typically, $\eps,\delta$ are small (and
$\delta=2^{-k}$ captures the case where $f$ is
worst-case hard). Achieving $\eps = 1/n^{\omega(1)}$
is a prerequisite for cryptography and most
pseudorandom-generator constructions.
In this paper we study the complexity of black-box
proofs of hardness amplification. A class of circuits
$\cal D$ {\em proves} a hardness amplification result
if for any function $h$ that agrees with $Amp(f)$ on a
$1/2+\e$ fraction of the inputs there exists an oracle
circuit $D \in \cal D$ such that $D^h$ agrees with $f$
on a $1-\delta$ fraction of the inputs. We focus on
the case where every $D \in \cal D$ makes
\emph{non-adaptive} queries to $h$. This setting
captures most hardness amplification techniques. We
prove two main results:
\begin{enumerate}
\item The circuits in $\ckt$ ``can be used'' to compute the
majority function on $1/\e$ bits. In particular, these circuits have
large depth when $\eps \leq 1/\poly \log n$.
\item The circuits in $\ckt$ must make
$\Omega\rob{\log(1/\delta)/\e^2}$ oracle queries.
\end{enumerate}
Both our bounds on the depth and on the number of queries
are tight up to constant factors.
Our results explain why hardness amplification
techniques have failed to transform known lower bounds
against constant-depth circuit classes into strong
average-case lower bounds. When coupled with the
celebrated ``Natural Proofs'' result by Razborov and
Rudich (J.~CSS '97) and the pseudorandom functions by
Naor and Reingold (J.~ACM '04), our results show that
\emph{standard techniques for hardness amplification
can only be applied to those circuit classes for which
standard techniques cannot prove circuit lower
bounds.}
Our results reveal a contrast between {\em Yao's XOR
Lemma} ($Amp(f) \eqdef f(x_1) \oplus \ldots \oplus
f(x_t) \in \zo$) and the {\em Direct-Product Lemma}
($Amp(f) \eqdef f(x_1) \circ \ldots \circ f(x_t) \in
\zo^t$; here $Amp(f)$ is non-Boolean). Our results (1)
and (2) apply to Yao's XOR lemma, whereas known proofs
of the direct-product lemma violate both (1) and (2).
One of our contributions is a new technique to handle
``non-uniform'' reductions, i.e.~the case when $\cal
D$ contains many circuits. This technique may be
useful in arguing about non-uniform black-box proofs
for other primitives.
