Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR10-186 | 2nd December 2010 19:01

On beating the hybrid argument

TR10-186
Authors: Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola
Publication: 2nd December 2010 19:01
Keywords:

Abstract:

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

ISSN 1433-8092 | Imprint