Improved pseudorandomness for unordered branching programs through local monotonicity
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal · 2018
We present an explicit pseudorandom generator with seed length Õ((logn)w+1) for read-once, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impagliazzo, Meka and Zuckerman (FOCS’12) where they required seed length n1/2+o(1).