# Pseudorandomness for Width-2 Branching Programs

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

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1rk0r`

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.