On beating the hybrid argument
On beating the hybrid argument
复制标题
关于击败混合论点
DOI：
10.1145/2090236.2090273
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Bill Fefferman;Ronen Shaltiel;C. Umans;Emanuele Viola
混合论证使人们能够将一个分布（与均匀分布）的可区分性与给定前缀下单个比特的可预测性联系起来。该论证会产生一个等于分布比特长度的因子\(k\)的损失：\(\varepsilon\) - 可区分性意味着\(\varepsilon/k\) - 可预测性。本文研究了避免这种损失的结果——我们称之为“战胜混合论证”——并开发了在某些自然设定下规避这种损失的新证明技术。具体而言，我们得到了以下结果：
1. 我们给出了尼散 - 维格德森生成器（《计算机与系统科学杂志》1994年）的一个实例，它可被量子计算机破解，并且对于\(AC_0\)是\(o(1)\) - 不可预测的。我们推测这个生成器确实能欺骗\(AC_0\)。我们的推测意味着存在一个谕示，相对于该谕示\(BQP\)不在多项式分层\(PH\)中，这是一个长期未解决的问题。
2. 我们表明，因帕利亚佐、尼散和维格德森（《计算理论年会》1994年）提出的“INW”生成器，其种子长度为\(O(\log n\log\log n)\)，所产生的分布对于多项对数宽度（一般的）只读无感知分支程序是\(1 / \log n\) - 不可预测的。得到输出与均匀分布不可区分的此类生成器是一个长期未解决的问题。
3. 我们确定了函数\(f\)的一个性质，“可重采样性”，它使我们在论证
[公式]
与均匀分布的不可区分性时能够战胜混合论证。这为诸如\(AC_0[p]\)之类的类给出了新的伪随机生成器，其拉伸尽管是次线性的，但却是已知最大的。我们将此视为在分析尼散 - 维格德森生成器（它将[公式]应用于相关的\(x_1,\ldots,x_k\)）以及证明第一项中的推测方面战胜混合论证的第一步。
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.