Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2020 | Submitted
Journal Article Open

Pseudorandom Bits for Oblivious Branching Programs

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

Created:
August 19, 2023
Modified:
October 19, 2023