Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 14, 2013 | Published
Journal Article Open

On Beating the Hybrid Argument

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. Our main results are: 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 AC⁰. We conjecture that this generator indeed fools AC⁰. 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. (This was also observed by other researchers.) 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 G^(⊗k)_f(x₁,…,x_k)=(x₁,f(x₁),x₂,f(x₂),…,x_k,f(x_k)) from uniform. This gives new pseudorandom generators for classes such as AC⁰ [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^(⊗k)_f on correlated x₁,…,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.

Additional Information

© 2013 Bill Fefferman, Ronen Shaltiel, Christopher Umans and Emanuele Viola. Licensed under a Creative Commons Attribution License (CC-BY). Received: February 23, 2012; Revised: July 31, 2013; Published: November 14, 2013. An extended abstract of this paper appeared in the Proceedings of the 3rd Innovations in Theoretical Computer Science (ITCS) 2012. Supported by IQI. Supported by BSF grant 2010120, ISF grants 686/07, 864/11 and ERC starting grant 279559. Supported by NSF CCF-0846991, CCF-1116111 and BSF grant 2010120. Supported by NSF grant CCF-0845003.

Attached Files

Published - v009a026.pdf

Files

v009a026.pdf
Files (393.8 kB)
Name Size Download all
md5:0eb09c307ec8e1ceb74e4c59f363d19e
393.8 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 18, 2023