TR10-186 Authors: Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

Publication: 2nd December 2010 19:01

Downloads: 3311

Keywords:

The {\em hybrid argument}

allows one to relate

the {\em distinguishability} of a distribution (from

uniform) to the {\em

predictability} of individual bits given a prefix. The

argument incurs a loss of a factor $k$ equal to the

bit-length of the

distributions: $\epsilon$-distinguishability implies only

$\epsilon/k$-predictability. This paper studies the

consequences of avoiding

this loss -- what we call ``beating the hybrid argument''

-- and develops new proof techniques that circumvent the

loss in certain natural settings. Specifically, we obtain

the following results:

\begin{enumerate}

\item We give an instantiation of the Nisan-Wigderson

generator (JCSS '94) that can be broken by

quantum computers, and that is

$o(1)$-unpredictable

against $AC^0$. This is not enough to imply

indistinguishability via the hybrid argument

because of the hybrid-argument loss; nevertheless, we

conjecture that this generator indeed fools $AC^0$,

and we prove this

statement for a simplified version of the problem.

Our conjecture implies the existence of an oracle

relative to which BQP is not in the PH, a

longstanding open problem.

\item We show that the ``INW'' generator by

Impagliazzo, Nisan, and Wigderson (STOC '94) with

seed length $O(\log n \log \log n)$ produces a

distribution that is $1/\log n$-unpredictable

against poly-logarithmic width (general)

read-once oblivious branching programs. Thus

avoiding the hybrid-argument loss would lead to a

breakthrough in generators against small space.

\item We study pseudorandom generators obtained from

a hard function by {\em repeated sampling}. We

identify a property of

functions, ``resamplability,'' that allows us to beat

the hybrid argument, leading to new pseudorandom

generators for $AC^0[p]$

and similar classes. Although the generators have

sub-linear stretch, they represent the best-known

generators for these classes.

\end{enumerate}

Thus we establish that ``beating'' or bypassing the

hybrid argument would have two significant consequences

in complexity, and we take steps toward that goal by

developing techniques that indeed beat the hybrid

argument in related (but simpler) settings, leading to

best-known PRGs for certain complexity classes.