Name
Title | ||
|---|---|---|
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity. |
Abstract | ||
|---|---|---|
We present an explicit pseudorandom generator with seed length Õ((logn)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 Impagliazzo, Meka and Zuckerman (FOCS’12) where they required seed length n1/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→ {0,1}, any k ∈ {1,…,n}, [complex formula not displayed]
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.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3188745.3188800 | STOC '18: Symposium on Theory of Computing
Los Angeles
CA
USA
June, 2018 |
Keywords | DocType | ISSN |
Branching programs,Fourier analysis,pseudorandom generators,small-space computation,space-bounded computation,random restrictions | Conference | 0737-8017 |
ISBN | Citations | PageRank |
978-1-4503-5559-9 | 1 | 0.35 |
References | Authors | |
12 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eshan Chattopadhyay | 1 | 84 | 11.71 |
| Pooya Hatami | 2 | 94 | 14.40 |
| Omer Reingold | 3 | 3369 | 232.46 |
| Avishay Tal | 4 | 58 | 11.83 |