Skip to main content

Pseudorandom Generators for Regular Branching Programs

Author(s): Braverman, Mark; Rao, Anup; Raz, Ran; Yehudayoff, Amir

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1gr86
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorRao, Anup-
dc.contributor.authorRaz, Ran-
dc.contributor.authorYehudayoff, Amir-
dc.date.accessioned2021-10-08T19:45:13Z-
dc.date.available2021-10-08T19:45:13Z-
dc.date.issued2014en_US
dc.identifier.citationBraverman, Mark, Anup Rao, Ran Raz, and Amir Yehudayoff. "Pseudorandom Generators for Regular Branching Programs." SIAM Journal on Computing 43, no. 3 (2014): 973-986. doi:10.1137/120875673en_US
dc.identifier.issn0097-5397-
dc.identifier.urihttps://homes.cs.washington.edu/~anuprao/pubs/spaceNov16withHitting.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1gr86-
dc.description.abstractWe 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 either 0 or 2, except for the first layer. 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 nonregular) 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. Finally, we show that the set of all binary strings with less than d nonzero entries forms a hitting set for regular width d branching programs.en_US
dc.format.extent973 - 986en_US
dc.language.isoen_USen_US
dc.relation.ispartofSIAM Journal on Computingen_US
dc.rightsAuthor's manuscripten_US
dc.titlePseudorandom Generators for Regular Branching Programsen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1137/120875673-
dc.identifier.eissn1095-7111-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
PseudorandomGeneratorsRegularBranchingPrograms.pdf342.11 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.