Published February 2020
| Submitted
Journal Article
Open
Pseudorandom Bits for Oblivious Branching Programs
- Creators
- Gurjar, Rohit
- Volk, Ben Lee
Abstract
We construct a pseudorandom generator that fools known-order read-k oblivious branching programs and, more generally, any linear length oblivious branching program. For polynomial width branching programs, the seed lengths in our constructions are O(n^(1−1/2^(k−1))) (for the read-k case) and O(n/log log n) (for the linear length case). Previously, the best construction for these models required seed length (1 − Ω(1))n.
Additional Information
© 2020 Association for Computing Machinery. Received November 2018; revised September 2019; accepted November 2019. The research leading to these results has received funding the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement number 257575 and from the Israel Science Foundation (grant number 552/16). We thank Andrej Bogdanov for useful comments on an earlier version of this text.Attached Files
Submitted - 1708.02054.pdf
Files
1708.02054.pdf
Files
(200.9 kB)
Name | Size | Download all |
---|---|---|
md5:3a9331e1da5c5671083354413506064c
|
200.9 kB | Preview Download |
Additional details
- Eprint ID
- 101212
- DOI
- 10.1145/3378663
- Resolver ID
- CaltechAUTHORS:20200210-155003494
- 257575
- European Research Council (ERC)
- 552/16
- Israel Science Foundation
- Created
-
2020-02-11Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field