![pdf icon](/images/pdficon_large.png)
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 generators, 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: ϵ-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 G⊗kf(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 G⊗kf 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.