Michal Koucký
ABSTRACT
We prove that the pseudorandom generator introduced by Impagliazzo et al. (1994) with proper choice of parameters fools group products of a given finite group G. The seed length is O((|G|O(1) + log 1/δ)log n), where n is the length of the word and δ is the allowed error. The result implies that the pseudorandom generator with seed length O((2O(w log w) + log 1/δ)log n) fools read-once permutation branching programs of width w. As an application of the pseudorandom generator one obtains small-bias spaces for products over all finite groups Meka and Zuckerman (2009).
Supplemental Material
- N. Alon, O. Goldreich, J. Håstad, and R. Peralta. Simple construction of almost k-wise independent random variables. Random Structures and Alg., 3(3):289--304, 1992.Google Scholar
Cross Ref
- M. Ajtai, J. Komlós, and E. Szemerédi. Deterministic simulation in logspace. In Proc. of ACM Symp. on Theory of Computing (STOC), pages 132--140, 1987. Google ScholarDigital Library
- Y. Azar, R. Motwani, and J. Naor. Approximating arbitrary probability distributions using small sample spaces. Combinatorica, 18:151--171, 1998.Google ScholarCross Ref
- N. Alon and J. Spencer. The Probabilistic Method. John Wiley, 1992.Google Scholar
- D.A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC$^1$. J. of Comp. and System Sci., 38(1):150 -- 164, 1989. Google ScholarDigital Library
- L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols and logspace-hard pseudorandom sequences (extended abstract). In Proc. of ACM Symp. on Theory of Computing (STOC), pages 1--11, 1989. Google ScholarDigital Library
- M. Braverman, A. Rao, R. Raz, and A. Yehudayoff. Pseudorandom generators for regular branching programs. In Proc. of Symp. on Foundations of Computer Science (FOCS), pages 40--47, 2010. Google ScholarDigital Library
- J. Brody and E. Verbin. The coin problem, and pseudorandomness for branching programs. In Proc. of the fifty first annual Symp. on Foundations of Computer Science (FOCS), pages 30--39, 2010. Google ScholarDigital Library
- O. Gabber and Z. Galil. Explicit constructions of linear-sized superconcentrators. J. of Comp. and System Sci., 22(3):407--420, 1981.Google ScholarCross Ref
- R. Impagliazzo, N. Nisan, and A. Wigderson. Pseudorandomness for network algorithms. In Proc. of ACM Symp. on Theory of Computing (STOC), pages 356--364, 1994. Google ScholarDigital Library
- L. Lovász. Combinatorial Problems and Exercises. Akadémiai Kiadó, Budapest, 1993.Google Scholar
- S. Lovett, O. Reingold, L. Trevisan, and S. P. Vadhan. Pseudorandom bit generators that fool modular sums. In APPROX-RANDOM, pages 615--630, 2009. Google ScholarDigital Library
- R. Meka and D. Zuckerman. Small-bias spaces for group products. In APPROX-RANDOM, pages 658--672, 2009. Google ScholarDigital Library
- N. Nisan. Pseudorandom generators for space-bounded computations. Combinatorica, 12(4):449--461, 1992.Google ScholarCross Ref
- N. Nisan. RL ⊆ SC. Computational Complexity, 4(1):1--11, 1994. Google ScholarDigital Library
- J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. on Computing, 22(4):838--856, 1993. Google ScholarDigital Library
- N. Nisan and D. Zuckerman. Randomness is linear in space. J. of Comp. and System Sci., 52(1):43--52, 1996. Google ScholarDigital Library
- R. Raz and O. Reingold. On recycling the randomness of states in space bounded computation. In Proc. of ACM Symp. on Theory of Computing (STOC), pages 159--168, 1999. Google ScholarDigital Library
- E. Rozenman and S.P. Vadhan. Derandomized squaring of graphs. In APPROX-RANDOM, pages 436--447, 2005. Google ScholarDigital Library
- O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Annals of Mathematics, pages 157--187, 2000.Google ScholarCross Ref
- W.J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. of Comp. and System Sci., 4(2):177--192, 1970. Google ScholarDigital Library
- M.E. Saks and S. Zhou. BP_HSpace(S) ⊆ DSPACE(3/2). J. of Comp. and System Sci., 58(2):376--403, 1999. Google ScholarDigital Library
- J. S'ıma and S. Zák. A polynomial time construction of a hitting set for read-once branching programs of width 3. Technical Report TR10-088, Electronic Colloquium on Computational Complexity (ECCC), 2010.Google Scholar
Index Terms
- Pseudorandom generators for group products: extended abstract
Recommendations
Improved pseudorandom generators for depth 2 circuits
APPROX/RANDOM'10: Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniquesWe prove the existence of a poly(n,m)-time computable pseudorandom generator which "1/poly(n,m)-fools" DNFs with n variables and m terms, and has seed length O(log2nm ċ log log nm). Previously, the best pseudorandom generator for depth-2 circuits had ...
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer ScienceWe present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and ...
Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of ComputingAssume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this ...
Comments