Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR17-171 | 9th November 2017 00:43

#### Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revision #1
Authors: Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
Accepted on: 9th November 2017 00:43
Keywords:

Abstract:

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width $w$ read-once, oblivious branching program $B:\{0,1\}^n\rightarrow \{0,1\}$, any $k \in \{1,\ldots,n\}$, $$\sum_{S\subseteq[n]: |S|=k}|\widehat{B}(S)| \le O(\log n)^{wk}.$$ This settles a conjecture posed by Reingold, Steinke, and Vadhan (RANDOM'13).

Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs.

Changes to previous version:

Fixed a typo in the bibliography.

### Paper:

TR17-171 | 6th November 2017 08:05

#### Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

TR17-171
Authors: Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
Publication: 6th November 2017 15:07
Keywords:

Abstract:

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width $w$ read-once, oblivious branching program $B:\{0,1\}^n\rightarrow \{0,1\}$, any $k \in \{1,\ldots,n\}$, $$\sum_{S\subseteq[n]: |S|=k}|\widehat{B}(S)| \le O(\log n)^{wk}.$$ This settles a conjecture posed by Reingold, Steinke, and Vadhan (RANDOM'13).

Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs.

ISSN 1433-8092 | Imprint