TR07-130 Authors: Ronen Shaltiel, Emanuele Viola

Publication: 9th December 2007 14:48

Downloads: 3036

Keywords:

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.