文章基本信息

标题：Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs
本地全文：下载
作者：Thomas Steinke ; Salil Vadhan ; Andrew Wan 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2017
卷号：13
出版社：University of Chicago
摘要：We present an explicit pseudorandom generator for oblivious, read-once, width-33 branching programs, which can read their input bits in any order. The generator has seed length O˜(log3n).O~(log3⁡n). The best previously known seed length for this model is n1/2+o(1)n1/2+o(1) due to Impagliazzo, Meka, and Zuckerman (FOCS'12). Our result generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM'13) for permutation branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f:{0,1}n→{0,1}f:{0,1}n→{0,1} computed by such a branching program, and k∈[n],k∈[n],∑s⊆[n]:|s|=k∣∣fˆ[s]∣∣≤n2⋅(O(logn))k,∑s⊆[n]:|s|=k|f^[s]|≤n2⋅(O(log⁡n))k,where fˆ[s]=EU[f[U]⋅(−1)s⋅U]f^[s]=EU[f[U]⋅(−1)s⋅U] is the standard Fourier transform over Zn2Z2n. The base O(logn)O(log⁡n) of the Fourier growth is tight up to a factor of loglognlog⁡log⁡n.
关键词：pseudorandom generators; branching programs; Fourier analysis