Title: Pseudorandomness for Linear Length Branching Programs and Stack Machines

Abstract: We give a simple distribution that is pseudorandom against

(1) Oblivious branching programs over binary alphabet;
(2) Arbitrary branching programs over sufficiently large alphabet;
(3) Log-space randomized Turing Machines extended with a stack that make a constant number of passes over their random tape.

This distribution can be sampled by a pseudorandom generator with small linear stretch. These results are consequences of the following property of the distribution over {0, 1}^n: Given any pair of subsets I, J of size 0.99n each and boolean functions f, g: {0, 1}^{0.99n} -> {0, 1}, the joint distribution (f(x|I), g(x|J)) is statistically close in the case x is uniformly random and in the case x is chosen from the pseudorandom distribution.

This is joint work with Andrej Bogdanov and PeriklisPapakonstantinou.