Pseudorandomness for permutation and regular branching programs

Anindya De

doi:10.1109/CCC.2011.23

Pseudorandomness for permutation and regular branching programs

Anindya De^*

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

44 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 language	English (US)
Title of host publication	Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011
Pages	221-231
Number of pages	11
DOIs	https://doi.org/10.1109/CCC.2011.23
State	Published - Aug 29 2011
Event	26th Annual IEEE Conference on Computational Complexity, CCC 2011 - San Jose, CA, United States Duration: Jun 8 2011 → Jun 10 2011

Publication series

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

Other

Other	26th Annual IEEE Conference on Computational Complexity, CCC 2011
Country/Territory	United States
City	San Jose, CA
Period	6/8/11 → 6/10/11

Keywords

Branching programs
Expander products
INW generator

ASJC Scopus subject areas

Software
Theoretical Computer Science
Computational Mathematics

Access to Document

10.1109/CCC.2011.23

Cite this

@inproceedings{f3131df0e0e245418b493c879279f27d,

title = "Pseudorandomness for permutation and regular branching programs",

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{\'y} 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].",

keywords = "Branching programs, Expander products, INW generator",

author = "Anindya De",

year = "2011",

month = aug,

day = "29",

doi = "10.1109/CCC.2011.23",

language = "English (US)",

isbn = "9780769544113",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "221--231",

booktitle = "Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011",

note = "26th Annual IEEE Conference on Computational Complexity, CCC 2011 ; Conference date: 08-06-2011 Through 10-06-2011",

}

De, A 2011, Pseudorandomness for permutation and regular branching programs. in Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011., 5959811, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 221-231, 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, CA, United States, 6/8/11. https://doi.org/10.1109/CCC.2011.23

TY - GEN

T1 - Pseudorandomness for permutation and regular branching programs

AU - De, Anindya

PY - 2011/8/29

Y1 - 2011/8/29

N2 - 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].

AB - 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].

KW - Branching programs

KW - Expander products

KW - INW generator

UR - http://www.scopus.com/inward/record.url?scp=80052007561&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052007561&partnerID=8YFLogxK

U2 - 10.1109/CCC.2011.23

DO - 10.1109/CCC.2011.23

M3 - Conference contribution

AN - SCOPUS:80052007561

SN - 9780769544113

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 221

EP - 231

BT - Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011

T2 - 26th Annual IEEE Conference on Computational Complexity, CCC 2011

Y2 - 8 June 2011 through 10 June 2011

ER -

Pseudorandomness for permutation and regular branching programs

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this