Document Open Access Logo

Log-Seed Pseudorandom Generators via Iterated Restrictions

Authors Dean Doron , Pooya Hatami , William M. Hoza

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.6.pdf
  • Filesize: 0.71 MB
  • 36 pages

Document Identifiers

Author Details

Dean Doron
  • Department of Computer Science, Stanford University, CA, USA
Pooya Hatami
  • Department of Computer Science & Engineering, Ohio State University, Columbus, OH, USA
William M. Hoza
  • Department of Computer Science, University of Texas at Austin, TX, USA

Funding

  • Doron, Dean: Supported by NSF grant CCF-1763311. Part of this work was done while at UT Austin and supported by NSF grant CCF-1705028.
  • Hatami, Pooya: Supported by NSF grant CCF-1947546. Part of this work was done while at UT Austin and supported by a Simons Investigator Award (#409864, David Zuckerman).
  • Hoza, William M.: Supported by the NSF GRFP under Grant DGE-1610403 and by a Harrington Fellowship from UT Austin.

Acknowledgements

We thank David Zuckerman for very helpful discussions.

Cite As Get BibTex

Dean Doron, Pooya Hatami, and William M. Hoza. Log-Seed Pseudorandom Generators via Iterated Restrictions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 6:1-6:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.6

Abstract

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The "iterated restrictions" approach, pioneered by Ajtai and Wigderson [Ajtai and Wigderson, 1989], has provided PRGs with seed length polylog n or even Õ(log n) for several restricted models of computation. Can this approach ever achieve the optimal seed length of O(log n)?
In this work, we answer this question in the affirmative. Using the iterated restrictions approach, we construct an explicit PRG for read-once depth-2 AC⁰[⊕] formulas with seed length O(log n) + Õ(log(1/ε)). In particular, we achieve optimal seed length O(log n) with near-optimal error ε = exp(-Ω̃(log n)). Even for constant error, the best prior PRG for this model (which includes read-once CNFs and read-once 𝔽₂-polynomials) has seed length Θ(log n ⋅ (log log n)²) [Chin Ho Lee, 2019]. 
A key step in the analysis of our PRG is a tail bound for subset-wise symmetric polynomials, a generalization of elementary symmetric polynomials. Like elementary symmetric polynomials, subset-wise symmetric polynomials provide a way to organize the expansion of ∏_{i=1}^m (1 + y_i). Elementary symmetric polynomials simply organize the terms by degree, i.e., they keep track of the number of variables participating in each monomial. Subset-wise symmetric polynomials keep track of more data: for a fixed partition of [m], they keep track of the number of variables from each subset participating in each monomial. Our tail bound extends prior work by Gopalan and Yehudayoff [Gopalan and Yehudayoff, 2014] on elementary symmetric polynomials.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Pseudorandom generators
  • Pseudorandom restrictions
  • Read-once depth-2 formulas
  • Parity gates

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in LOGSPACE. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC), pages 132-140, New York, NY, USA, 1987. ACM. URL: https://doi.org/10.1145/28395.28410.
  2. Miklos Ajtai and Avi Wigderson. Deterministic simulation of probabilistic constant depth circuits. Advances in Computing Research, 5(199-222):1, 1989. Google Scholar
  3. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures &Algorithms, 3(3):289-304, 1992. Google Scholar
  4. Louay Bazzi and Nagi Nahas. Small-bias is not enough to hit read-once CNF. Theory of Computing Systems, 60(2):324-345, February 2017. URL: https://doi.org/10.1007/s00224-016-9680-6.
  5. Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM Journal on Computing, 0(0):STOC18-242-STOC18-299, 2020. URL: https://doi.org/10.1137/18M1197734.
  6. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. SIAM Journal on Computing, 43(3):973-986, 2014. Google Scholar
  7. J. Brody and E. Verbin. The coin problem and pseudorandomness for branching programs. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 30-39, October 2010. URL: https://doi.org/10.1109/FOCS.2010.10.
  8. Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan. Improved algorithms via approximations of probability distributions. Journal of Computer and System Sciences, 61(1):81-107, 2000. URL: https://doi.org/10.1006/jcss.1999.1695.
  9. Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal. Improved pseudorandomness for unordered branching programs through local monotonicity. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 363-375, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3188745.3188800.
  10. Sitan Chen, Thomas Steinke, and Salil Vadhan. Pseudorandomness for read-once, constant-depth circuits. arXiv preprint, 2015. URL: http://arxiv.org/abs/1504.04675.
  11. Anindya De. Pseudorandomness for permutation and regular branching programs. In Proceedings of the 26th Annual IEEE 26th Annual Conference on Computational Complexity (CCC), pages 221-231. IEEE, 2011. Google Scholar
  12. Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Approximation, randomization, and combinatorial optimization, volume 6302 of Lecture Notes in Computer Science, pages 504-517. Springer, Berlin, 2010. URL: https://doi.org/10.1007/978-3-642-15369-3_38.
  13. Dean Doron, Pooya Hatami, and William M Hoza. Near-optimal pseudorandom generators for constant-depth read-once formulas. In 34th Computational Complexity Conference (CCC), 2019. Google Scholar
  14. Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2018. Google Scholar
  15. Anat Ganor and Ran Raz. Space pseudorandom generators by communication complexity lower bounds. In LIPIcs-Leibniz International Proceedings in Informatics, volume 28. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  16. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 120-129. IEEE, 2012. Google Scholar
  17. Parikshit Gopalan and Amir Yehudayoff. Inequalities and tail bounds for elementary symmetric polynomial with applications. arXiv preprint, 2014. URL: http://arxiv.org/abs/1402.3543.
  18. Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM Journal on Computing, 47(2):493-523, 2018. URL: https://doi.org/10.1137/17M1129088.
  19. William M. Hoza and David Zuckerman. Simple optimal hitting sets for small-success RL. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2018. Google Scholar
  20. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing (STOC), pages 356-364. ACM, 1994. Google Scholar
  21. Michal Koucký, Prajakta Nimbhorkar, and Pavel Pudlák. Pseudorandom generators for group products. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 263-272. ACM, New York, 2011. URL: https://doi.org/10.1145/1993636.1993672.
  22. Chin Ho Lee. Fourier bounds and pseudorandom generators for product tests. In Amir Shpilka, editor, 34th Computational Complexity Conference (CCC), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:25, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.7.
  23. Chin Ho Lee and Emanuele Viola. More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. In Electronic Colloquium on Computational Complexity (ECCC), volume 24, page 167, 2017. Google Scholar
  24. Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 626-637. ACM, New York, 2019. Google Scholar
  25. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838-856, 1993. Google Scholar
  26. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. Google Scholar
  27. Noam Nisan. RL ⊆ SC. computational complexity, 4(1):1-11, March 1994. URL: https://doi.org/10.1007/BF01205052.
  28. Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. URL: https://doi.org/10.1006/jcss.1996.0004.
  29. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4):Art. 17, 24, 2008. URL: https://doi.org/10.1145/1391289.1391291.
  30. Omer Reingold, Thomas Steinke, and Salil Vadhan. Pseudorandomness for regular branching programs via Fourier analysis. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 655-670. Springer, 2013. Google Scholar
  31. Michael E. Saks and Shiyu Zhou. BP_HSPACE(S) ⊆ DSPACE(S^3/2). Journal of Computer and System Sciences, 58(2):376-403, 1999. Google Scholar
  32. Thomas Steinke. Pseudorandomness for permutation branching programs without the group theory. In Electronic Colloquium on Computational Complexity (ECCC), 2012. Google Scholar
  33. Thomas Steinke, Salil Vadhan, and Andrew Wan. Pseudorandomness and Fourier-growth bounds for width-3 branching programs. Theory of Computing, 13(12):1-50, 2017. URL: https://doi.org/10.4086/toc.2017.v013a012.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact