The hybrid argument allows one to relate the distinguishability of a distribution (from uniform)

to the predictability of individual bits given a prefix. The argument incurs a loss of a factor

k equal to the bit-length of the distributions: -distinguishability implies only /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:

1. 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 AC0

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

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

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

3. We study pseudorandom generators obtained from a hard function by repeated sampling.

We identify a property of functions, “resamplability,” that allows us to beat the hybrid argument,

leading to new pseudorandom generators for AC0

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