Volume 9 (2013)
Article 26 pp. 809-843

On Beating the Hybrid Argument

Received: February 23, 2012

Revised: July 31, 2013

Published: November 14, 2013

Revised: July 31, 2013

Published: November 14, 2013

**Keywords:**complexity theory, pseudorandom generator, BQP, hybrid argument, circuits, branching programs

**Categories:**complexity theory, quantum computing, pseudorandom generator, BQP, polynomial-time hierarchy, PH, hybrid argument, circuits, branching programs

**ACM Classification:**F.1.3, F.2.3

**AMS Classification:**81P68, 68Q15

**Abstract:**
[Plain Text Version]

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:
$\epsilon$-distinguishability implies $\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. Our main results are:

- 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$. We conjecture that this generator indeed fools $AC^0$. Our conjecture implies the existence of an oracle relative to which BQP is not in the PH, a longstanding open problem.
- 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. (This was also observed by other researchers.) Obtaining such generators where the output is indistinguishable from uniform is a longstanding open problem.
- We identify a property of functions $f$, “resamplability,” that allows us to beat the hybrid argument when arguing indistinguishability of \[G^{\otimes k}_f(x_1,\ldots,x_k) = (x_1,f(x_1),x_2,f(x_2),\ldots,x_k,f(x_k))\] from uniform. This gives new pseudorandom generators for classes such as $AC^0[p]$ with a stretch that, despite being sub-linear, is the largest known. We view this as a first step towards beating the hybrid argument in the analysis of the Nisan-Wigderson generator (which applies $G^{\otimes k}_f$ on correlated $x_1,\ldots,x_k$) and proving the conjecture in the first item.

An extended abstract of this paper appeared in the Proceedings of the 3rd Innovations in Theoretical Computer Science (ITCS) 2012.