文章基本信息

标题：Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs
本地全文：下载
作者：Thomas Steinke ; Salil Vadhan ; Andrew Wan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：885-899
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.885
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length O~( log^3 n ). The previously best known seed length for this model is n^{1/2+o(1)} due to Impagliazzo, Meka, and Zuckerman (FOCS'12). Our work 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} computed by such a branching program, and k in [n], sum_{|s|=k} |hat{f}(s)| is the standard Fourier transform over Z_2^n. The base O(log n) of the Fourier growth is tight up to a factor of log log n.
关键词：Pseudorandomness; Branching Programs; Discrete Fourier Analysis