期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give new pseudorandom generators for \emph{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((logd+loglogn+log(1))logn)
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 22 .
