Pseudorandom Generators from Polarizing Random Walks
Pseudorandom Generators from Polarizing Random Walks
复制标题
极化随机游走的伪随机生成器
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Shachar Lovett
中科院分区：
文献类型：
--
作者：
Eshan Chattopadhyay;Pooya Hatami;Kaave Hosseini;Shachar Lovett
我们提出了一个新的框架，用于构建用于n variate boolean函数的伪随机生成器。它基于两个新概念。首先，我们介绍了分数伪和生成器，这些生成器是伪分布，以[-1，1] n中的值为单位。接下来，我们使用分数伪和生成器作为在[-1，1] N中随机步行的步骤，该步骤将收敛到{-1，1} n。我们证明，由于极化，这种随机步行会迅速收敛（随着时间的时间对数）。作为应用程序，我们为带有有限的傅立叶尾巴的布尔函数构造了伪随机生成器。我们使用它来获取具有灵敏度s的函数的伪随机生成器，其种子长度在s中是多项式。其他示例包括通过各种分支程序或有界深度电路计算的功能。
We propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1, 1]n. Next, we use a fractional pseudorandom generator as steps of a random walk in [-1, 1]n that converges to {-1, 1}n. We prove that this random walk converges fast (in time logarithmic in n) due to polarization. As an application, we construct pseudorandom generators for Boolean functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for functions with sensitivity s, whose seed length is polynomial in s. Other examples include functions computed by branching programs of various sorts or by bounded depth circuits.