Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

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

Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revision #1
Authors: Omer Reingold, Thomas Steinke, Salil Vadhan
Accepted on: 20th June 2013 00:07
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

TR13-086
Authors: Omer Reingold, Thomas Steinke, Salil Vadhan
Publication: 13th June 2013 07:07
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)^{2k}\$ at level \$k\$, independent of the length of the program.

ISSN 1433-8092 | Imprint