Pseudorandomness for permutation and regular branching programs

Anindya De*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations

Abstract

In this paper, we prove the following results about the INW pseudorandom generator: • It fools constant width permutation branching programs with error e using a seed of length O(logn · log(1/ε)). • It fools constant width regular branching programs with error ε using a seed of length O(logn · (log log n + log(1/ε))). These results match the recent results of Koucký et al. (STOC 2011) and Braverman et al. and Brody and Verbin (FOCS 2010). However, our analysis gives a better dependence of the seed length on the width for permutation branching programs than the results of Koucky et al. (STOC 2011). Perhaps, more significantly, our proof method is entirely different and linear algebraic in nature as opposed to the group theoretic methods of [1] and the information theoretic and probabilistic methods of [2], [3]. Along the way, we also obtain pseudorandom generators for the "small biased spaces" for group products [4] with a seed length O(logn · (log G| +log(1/ε))). Previously, it was possible to get O(logn ε (|G| O(1) +log(1/ε))) using the pseudorandom generator of [1].

Original languageEnglish (US)
Title of host publicationProceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011
Pages221-231
Number of pages11
DOIs
StatePublished - Aug 29 2011
Event26th Annual IEEE Conference on Computational Complexity, CCC 2011 - San Jose, CA, United States
Duration: Jun 8 2011Jun 10 2011

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other26th Annual IEEE Conference on Computational Complexity, CCC 2011
CountryUnited States
CitySan Jose, CA
Period6/8/116/10/11

Keywords

  • Branching programs
  • Expander products
  • INW generator

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Pseudorandomness for permutation and regular branching programs'. Together they form a unique fingerprint.

  • Cite this

    De, A. (2011). Pseudorandomness for permutation and regular branching programs. In Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011 (pp. 221-231). [5959811] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2011.23