Skip to main content

Pseudorandomness for Width-2 Branching Programs

Author(s): Bogdanov, Andrej; Dvir, Zeev; Verbin, Elad; Yehudayoff, Amir

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).
Publication Date: 2013
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
DOI: 10.4086/toc.2013.v009a007
ISSN: 1557-2862
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.