Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
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
Download article from ToC site:
[PDF (384K)] [PS (1672K)] [Source ZIP]
Keywords: complexity theory, pseudorandom generator, BQP, 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: ϵ-distinguishability implies ϵ/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 AC0. We conjecture that this generator indeed fools AC0. 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(lognloglogn) produces a distribution that is 1/logn-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 Gkf(x1,,xk)=(x1,f(x1),x2,f(x2),,xk,f(xk)) from uniform. This gives new pseudorandom generators for classes such as AC0[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 Gkf on correlated x1,,xk) 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.