Loading...
Please wait, while we are loading the content...
Similar Documents
Pseudorandom generators for regular branching programs (2010)
| Content Provider | CiteSeerX |
|---|---|
| Author | Braverman, Mark Rao, Anup Raz, Ran Yehudayoff, Amir |
| Description | We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is (0 or) 2. For every width d and length n, our pseudorandom generator uses a seed of length O((log d + log log n + log(1/ɛ)) log n) to produce n bits that cannot be distinguished from a uniformly random string by any regular width d length n read-once branching program, except with probability ɛ. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly non-regular) branching program of length n and width d has the property that every vertex in the program is traversed with probability at least γ on a uniformly random input, then the error of the generator above is at most 2ɛ/γ 2. 1 In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science |
| File Format | |
| Language | English |
| Publisher Date | 2010-01-01 |
| Access Restriction | Open |
| Subject Keyword | Small Width Pseudorandom Generator Small Probability Regular Read-once Branching Program Uniformly Random Input Log Log Log Log Regular Branching Program New Pseudorandom Generator Uniformly Random String Branching Program General Read-once Branching Program |
| Content Type | Text |
| Resource Type | Article |
