Name
Abstract | ||
|---|---|---|
We prove the existence of a polynomial time computable pseudorandom generator that $\epsilon$-fools constant width regular read-once branching programs of length $n$ using a seed of length $O(\log n \cdot \log(1/\epsilon)) $. The previous best pseudorandom generator for regular branching programs used a seed of length $O(\log n \cdot (\log \log n + \log (1/\epsilon) )$, and was due to Braverman et. al. and Brody and Verbin (FOCS 2010). Our pseudorandom generator is the INW generator due to Impagliazzo et. al. (STOC 1994). Our work shares some similarity with the recent work of Kouck\'{y} et. al. (STOC 2011)who get similar seed length for permutation branching programs. However, our work proceeds by analyzing the eigenvalues of the stochastic matrices that arise in the transitions of the branching program which arguably makes the technique more robust. As a corollary of our techniques, we present new results on the ``small biased spaces for group products'' problem by Meka and Zuckerman (RANDOM 2009). We get a pseudorandom generator with seed length $ \log n \cdot (\log |G|+ \log (1/\epsilon))$. Previously, using the result of Kouck\'{y} et. al., it was possible to get a seed length of $\log n \cdot (|G|^{O(1)} + \log (1/\epsilon))$ for this problem. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/CCC.2011.23 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
computational complexity,linear algebra,probability,random number generation,INW pseudorandom generator,linear algebra,permutation branching programs,probabilistic methods,regular branching programs,INW generator,branching programs,expander products | Discrete mathematics,Binary logarithm,Combinatorics,Polynomial,Matrix (mathematics),Pseudorandomness,Permutation,Random number generation,Time complexity,Pseudorandom generator,Mathematics | Conference |
ISSN | ISBN | Citations |
1093-0159 E-ISBN : 978-0-7695-4411-3 | 978-0-7695-4411-3 | 17 |
PageRank | References | Authors |
0.69 | 16 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anindya De | 1 | 239 | 24.77 |