Name
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: ε-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. 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. 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. 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. Obtaining such generators where the output is indistinguishable from uniform is a longstanding open problem. 3. We identify a property of functions f, "resamplability," that allows us to beat the hybrid argument when arguing indistinguishability of [EQUATION] 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 [EQUATION] on correlated x1,...,xk) and proving the conjecture in the first item. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2090236.2090273 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
fools ac0,correlated x1,longstanding open problem,new proof technique,nisan-wigderson generator,new pseudorandom generator,n log log n,log n-unpredictable,hybrid argument,certain natural setting,pseudorandomness,quantum computing,quantum computer,branching program | Journal | 9 |
Issue | Citations | PageRank |
1 | 3 | 0.41 |
References | Authors | |
41 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bill Fefferman | 1 | 28 | 5.75 |
| Ronen Shaltiel | 2 | 953 | 51.62 |
| Christopher Umans | 3 | 879 | 55.36 |
| Emanuele Viola | 4 | 588 | 44.78 |