Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-186 | 2nd December 2010 19:01

On beating the hybrid argument



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:

\item We give an instantiation of the Nisan-Wigderson
generator (JCSS '94) that can be broken by
quantum computers, and that is
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.
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