02607nas a2200169 4500008004100000245003500041210003200076260001500108300001200123490000600135520215500141100002002296700002002316700002302336700002002359856005802379 2012 eng d00aOn Beating the Hybrid Argument0 aBeating the Hybrid Argument c2013/11/14 a809-8430 v93 aThe 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.
1 aFefferman, Bill1 aShaltiel, Ronen1 aUmans, Christopher1 aViola, Emanuele uhttp://users.cms.caltech.edu/~umans/papers/FSUV10.pdf02256nas a2200121 4500008004100000245005500041210005400096260001500150520188900165100002002054700002302074856003702097 2010 eng d00aPseudorandom generators and the BQP vs. PH problem0 aPseudorandom generators and the BQP vs PH problem c2010/07/023 a It is a longstanding open problem to devise an oracle relative to which BQP
does not lie in the Polynomial-Time Hierarchy (PH). We advance a natural
conjecture about the capacity of the Nisan-Wigderson pseudorandom generator
[NW94] to fool AC_0, with MAJORITY as its hard function. Our conjecture is
essentially that the loss due to the hybrid argument (which is a component of
the standard proof from [NW94]) can be avoided in this setting. This is a
question that has been asked previously in the pseudorandomness literature
[BSW03]. We then make three main contributions: (1) We show that our conjecture
implies the existence of an oracle relative to which BQP is not in the PH. This
entails giving an explicit construction of unitary matrices, realizable by
small quantum circuits, whose row-supports are "nearly-disjoint." (2) We give a
simple framework (generalizing the setting of Aaronson [A10]) in which any
efficiently quantumly computable unitary gives rise to a distribution that can
be distinguished from the uniform distribution by an efficient quantum
algorithm. When applied to the unitaries we construct, this framework yields a
problem that can be solved quantumly, and which forms the basis for the desired
oracle. (3) We prove that Aaronson's "GLN conjecture" [A10] implies our
conjecture; our conjecture is thus formally easier to prove. The GLN conjecture
was recently proved false for depth greater than 2 [A10a], but it remains open
for depth 2. If true, the depth-2 version of either conjecture would imply an
oracle relative to which BQP is not in AM, which is itself an outstanding open
problem. Taken together, our results have the following interesting
interpretation: they give an instantiation of the Nisan-Wigderson generator
that can be broken by quantum computers, but not by the relevant modes of
classical computation, if our conjecture is true.
1 aFefferman, Bill1 aUmans, Christopher uhttp://arxiv.org/abs/1007.0305v3