Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-122 | 28th July 2017 11:43

Pseudorandom Bits for Oblivious Branching Programs

RSS-Feed




TR17-122
Authors: Rohit Gurjar, Ben Lee Volk
Publication: 31st July 2017 10:16
Downloads: 1109
Keywords: 


Abstract:

We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $\tilde{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-\Omega(1))n$.



ISSN 1433-8092 | Imprint