Pseudorandomness via the Discrete Fourier Transform
Pseudorandomness via the Discrete Fourier Transform
复制标题
通过离散傅立叶变换实现伪随机性
DOI：
10.1109/focs.2015.60
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Raghu Meka
中科院分区：
文献类型：
--
作者：
Parikshit Gopalan;D. Kane;Raghu Meka
我们提出了一种新的方法，用于针对涉及计算输入线性函数的函数类别的无条件伪和发电机。我们给出了一个伪随机生成器的明确构造，该生成器以输入大小和所需的误差参数中的种子长度愚弄了线性函数的离散傅立叶变换。我们的结果提供了一个单个伪随机生成器，该生成器愚弄了文献中已考虑的日志空间中可计算的几类测试类别，包括一半空间（一般域），模块化测试和组合形状。对于所有这些类别，我们的生成器是第一个在输入长度和误差参数中都在对数种子长度附近实现的第一个。获得这样的种子长度本身就是一个自然的挑战，它需要克服，以使RL取代RL（复杂性理论中的一个核心问题）。我们的构建结合了从大量工作中的想法，从[1]的经典结构到最近逐渐增加[2] - [4]的独立范式，同时还引入了一些新型的分析机制，这些机械可能会发现其他应用程序。
We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an explicit construction of a pseudorandom generator that fools the discrete Fourier transforms of linear functions with seed-length that is nearly logarithmic (up to polyloglog factors) in the input size and the desired error parameter. Our result gives a single pseudorandom generator that fools several important classes of tests computable in log space that have been considered in the literature, including half spaces (over general domains), modular tests and combinatorial shapes. For all these classes, our generator is the first that achieves near logarithmic seed-length in both the input length and the error parameter. Getting such a seed-length is a natural challenge in its own right, which needs to be overcome in order to derandomize RL -- a central question in complexity theory. Our construction combines ideas from a large body of prior work, ranging from a classical construction of [1] to the recent gradually increasing independence paradigm of [2] -- [4], while also introducing some novel analytic machinery which might find other applications.