Pseudorandom Generators for Read-Once Monotone Branching Programs

Authors Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.58.pdf
  • Filesize: 0.78 MB
  • 21 pages

Document Identifiers

Author Details

Dean Doron
  • Department of Computer Science, Stanford University, CA, USA
Raghu Meka
  • Department of Computer Science, University of California at Los Angeles, CA, USA
Omer Reingold
  • Department of Computer Science, Stanford University, CA, USA
Avishay Tal
  • Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, CA, USA
Salil Vadhan
  • John A. Paulson School of Engineering & Applied Sciences, Harvard University, Cambridge, MA, USA

Acknowledgements

We are grateful to Kristoffer Hansen for pointing us to [Barrington et al., 1998] and explaining how their results imply Theorem 3.

Cite AsGet BibTex

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan. Pseudorandom Generators for Read-Once Monotone Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 58:1-58:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.58

Abstract

Motivated by the derandomization of space-bounded computation, there has been a long line of work on constructing pseudorandom generators (PRGs) against various forms of read-once branching programs (ROBPs), with a goal of improving the O(log² n) seed length of Nisan’s classic construction [Noam Nisan, 1992] to the optimal O(log n). In this work, we construct an explicit PRG with seed length Õ(log n) for constant-width ROBPs that are monotone, meaning that the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state. This result is complementary to a line of work that gave PRGs with seed length O(log n) for (ordered) permutation ROBPs of constant width [Braverman et al., 2014; Koucký et al., 2011; De, 2011; Thomas Steinke, 2012], since the monotonicity constraint can be seen as the "opposite" of the permutation constraint. Our PRG also works for monotone ROBPs that can read the input bits in any order, which are strictly more powerful than read-once AC⁰. Our PRG achieves better parameters (in terms of the dependence on the depth of the circuit) than the best previous pseudorandom generator for read-once AC⁰, due to Doron, Hatami, and Hoza [Doron et al., 2019]. Our pseudorandom generator construction follows Ajtai and Wigderson’s approach of iterated pseudorandom restrictions [Ajtai and Wigderson, 1989; Gopalan et al., 2012]. We give a randomness-efficient width-reduction process which proves that the branching program simplifies to an O(log n)-junta after only O(log log n) independent applications of the Forbes-Kelley pseudorandom restrictions [Michael A. Forbes and Zander Kelley, 2018].

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Circuit complexity
Keywords
  • Branching programs
  • pseudorandom generators
  • constant depth circuits

Metrics

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

References

  1. Miklos Ajtai and Avi Wigderson. Deterministic simulation of probabilistic constant depth circuits. Advances in Computing Research, 5(199-222):1, 1989. Google Scholar
  2. David A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. Journal of Computer and System Sciences, 38(1):150-164, 1989. Google Scholar
  3. David A. Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven Skyum. Searching constant width mazes captures the AC⁰ hierarchy. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), pages 73-83. Springer, 1998. Google Scholar
  4. David A. Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven Skyum. On monotone planar circuits. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC 1999), pages 24-31. IEEE, 1999. Google Scholar
  5. Andrej Bogdanov, Periklis A Papakonstaninou, and Andrew Wan. Pseudorandomness for read-once formulas. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), pages 240-246. IEEE, 2011. Google Scholar
  6. Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM Journal on Computing, 49(5):STOC18-242-STOC18-299, 2020. URL: https://doi.org/10.1137/18M1197734.
  7. 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
  8. J. Brody and E. Verbin. The coin problem and pseudorandomness for branching programs. In Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2012), pages 30-39, October 2010. URL: https://doi.org/10.1109/FOCS.2010.10.
  9. L. Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder. Balls and bins: Smaller hash families and faster evaluation. SIAM Journal on Computing, 42(3):1030-1050, 2013. Google Scholar
  10. 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 2018), pages 363-375. ACM, 2018. Google Scholar
  11. Sitan Chen, Thomas Steinke, and Salil Vadhan. Pseudorandomness for read-once, constant-depth circuits. arXiv preprint arXiv:1504.04675, 2015. Google Scholar
  12. Anindya De. Pseudorandomness for permutation and regular branching programs. In Proceedings of the 26th Annual IEEE 26th Annual Conference on Computational Complexity (CCC 2011), pages 221-231. IEEE, 2011. Google Scholar
  13. Dean Doron, Pooya Hatami, and William M. Hoza. Near-optimal pseudorandom generators for constant-depth read-once formulas. In Proceedings of the 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019. Google Scholar
  14. Dean Doron, Pooya Hatami, and William M. Hoza. Log-seed pseudorandom generators via iterated restrictions. In Proceedings of the 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  15. Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan. Monotone branching programs: Pseudorandomness and circuit complexity. In Electronic Colloquium on Computational Complexity (ECCC), number TR21-018, February 2021. Version 1. Google Scholar
  16. 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 2018). IEEE, 2018. Google Scholar
  17. Oded Goldreich. Three XOR-lemmas - an exposition. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 248-272. Springer, 2011. Google Scholar
  18. 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 2012), pages 120-129. IEEE, 2012. Google Scholar
  19. Iftach Haitner, Danny Harnik, and Omer Reingold. On the power of the randomized iterate. SIAM Journal on Computing, 40(6):1486-1528, 2011. Google Scholar
  20. 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.
  21. Alexander Healy, Salil Vadhan, and Emanuele Viola. Using nondeterminism to amplify hardness. SIAM Journal on Computing, 35(4):903-931, 2006. Google Scholar
  22. William M. Hoza, Edward Pyne, and Salil P. Vadhan. Pseudorandom generators for unbounded-width permutation branching programs. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 7:1-7:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.7.
  23. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC 1994), pages 356-364. ACM, 1994. Google Scholar
  24. Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM, 53(3):307-323, 2006. Google Scholar
  25. Adam R. Klivans, Homin Lee, and Andrew Wan. Mansour’s conjecture is true for random DNF formulas. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT 2010), 2010. Google Scholar
  26. 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 2011), pages 263-272. ACM, New York, 2011. URL: https://doi.org/10.1145/1993636.1993672.
  27. Chin Ho Lee. Fourier bounds and pseudorandom generators for product tests. In Proceedings of the 34th Computational Complexity Conference (CCC 2019), pages 7:1-7:25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  28. 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
  29. Michael Luby, Boban Velickovic, and Avi Wigderson. Deterministic approximate counting of depth-2 circuits. In Proceedings of the 2nd Annual Israel Symposium on Theory and Computing Systems (ISTCS 1993), pages 18-24. IEEE, 1993. Google Scholar
  30. 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 2019), pages 626-637. ACM, New York, 2019. Google Scholar
  31. Raghu Meka and David Zuckerman. Pseudorandom generators for polynomial threshold functions. SIAM Journal on Computing, 42(3):1275-1301, 2013. Google Scholar
  32. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838-856, 1993. Google Scholar
  33. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. Google Scholar
  34. 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
  35. D. Sivakumar. Algorithmic derandomization via complexity theory. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pages 619-626. ACM, 2002. Google Scholar
  36. John Steinberger. The distinguishability of product distributions by read-once branching programs. In Proceedings of the 28th IEEE Conference on Computational Complexity (CCC 2013), pages 248-254. IEEE, 2013. Google Scholar
  37. Thomas Steinke. Pseudorandomness for permutation branching programs without the group theory. Technical Report TR12-083, Electronic Colloquium on Computational Complexity (ECCC), July 2012. URL: http://eccc.hpi-web.de/report/2012/083/.
  38. Thomas Steinke, Salil Vadhan, and Andrew Wan. Pseudorandomness and Fourier-growth bounds for width-3 branching programs. Theory of Computing, 13(1):1-50, 2017. Google Scholar
  39. Yoav Tzur. Notions of weak pseudorandomness and GF(2ⁿ)-polynomials. Master’s thesis, Weizmann Institute of Science, 2009. Google Scholar
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