Theory of Computing
-------------------
Title     : On Beating the Hybrid Argument
Authors   : Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola
Volume    : 9
Number    : 26
Pages     : 809-843
URL       : https://theoryofcomputing.org/articles/v009a026

Abstract
--------

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.