Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-086 | 20th June 2013 00:07

Pseudorandomness for Regular Branching Programs via Fourier Analysis

RSS-Feed




Revision #1
Authors: Omer Reingold, Thomas Steinke, Salil Vadhan
Accepted on: 20th June 2013 00:07
Downloads: 2683
Keywords: 


Abstract:

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, which follows as a special
case of a generator due to Impagliazzo, Meka, and Zuckerman (FOCS 2012) (which gives a seed length of
$s^{1/2+o(1)}$ for arbitrary branching programs of size $s$). Our techniques also give seed length $n^{1/2+o(1)}$ for general oblivious, read-once branching programs of width $2^{n^{o(1)}}$, which is incomparable to the results of Impagliazzo et al.

Our pseudorandom generator is similar to the one used by Gopalan et al. (FOCS 2012) for read-once CNFs, but the analysis is quite different; ours is based on Fourier analysis of branching programs. In particular, we show that an oblivious, read-once, regular branching program of width $w$ has Fourier mass at most $(2w^2)^k$ at level $k$, independent of the length of the program.



Changes to previous version:

Typos and minor edits including statement of Thm 1.2.


Paper:

TR13-086 | 13th June 2013 05:13

Pseudorandomness for Regular Branching Programs via Fourier Analysis


Abstract:

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, which follows as a special
case of a generator due to Impagliazzo, Meka, and Zuckerman (FOCS 2012) (which gives a seed length of
$s^{1/2+o(1)}$ for arbitrary branching programs of size $s$). Our techniques also give seed length $n^{1/2+o(1)}$ for general oblivious, read-once branching programs of width $2^{n^{o(1)}}$, which is incomparable to the results of Impagliazzo et al.

Our pseudorandom generator is similar to the one used by Gopalan et al. (FOCS 2012) for read-once CNFs, but the analysis is quite different; ours is based on Fourier analysis of branching programs. In particular, we show that an oblivious, read-once, regular branching program of width $w$ has Fourier mass at most $(2w)^{2k}$ at level $k$, independent of the length of the program.



ISSN 1433-8092 | Imprint