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.
