To refer to this page use:
|Abstract:||We show that pseudorandom generators that fool degree-k polynomials over 𝔽2 also fool branching programs of width-2 and polynomial length that read k bits of input at a time. This model generalizes polynomials of degree k over 𝔽2 and includes some other interesting classes of functions, for instance, k-DNFs. The proof essentially follows by a new decomposition theorem for width-2 branching programs. The theorem states that if f can be computed by a width-2 branching program that reads k bits of input at a time, then f can be (roughly) written as a sum f=∑iαifi where each fi is a degree-k polynomial and ∑i|αi| is small. Bogdanov and Viola (FOCS 2007) constructed a pseudorandom generator that fools degree-k polynomials over 𝔽2 for arbitrary k. Their construction consists of summing k independent copies of a generator that ϵ-fools linear functions. Our second result investigates the limits of such constructions: We show that, in general, such a construction is not pseudorandom against bounded fan-in circuits of depth O((log(klog1/ϵ))2).|
|Citation:||Bogdanov, Andrej, Zeev Dvir, Elad Verbin, and Amir Yehudayoff. "Pseudorandomness for Width-2 Branching Programs." Theory of Computing 9, no. 7 (2013): pp. 283-293. doi:10.4086/toc.2013.v009a007|
|Pages:||283 - 293|
|Type of Material:||Journal Article|
|Journal/Proceeding Title:||Theory of Computing|
|Version:||Final published version. This is an open access article.|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.